Leetcode题目总结1-二分法

二分法看似简单，实际上有很多问题都比较麻烦，比如：mid取整方式，区间开闭，序列是否有重复元素，会不会越界，会不会死循环······ 在网上参考了许多前辈的写法，各有优劣，但始终不是特别满意。这里主要参照知乎用户LightGHLi的写法，算是比较清楚覆盖面比较好的写法。

1. 二分法的解决思路

从问题上说二分查找分三大类：无重复序列找具体值，无重复序列找上下界，有重复序列找上下界。将他们归为四类模板，皆针对不下降序列（有重复无重复都可以）。

看起来很复杂，其实记忆方法很简单：

情况	条件
求最小的i	mid向下取整，l快r缓，返回r，if(nums[mid] < target) l=mid+1
求最大的i	mid向上取整，r快l缓，返回l，if(nums[mid] > target) r=mid-1

取整方式有两种：

int mid =(l+r) / 2; //向下取整
int mid=(l+r+1)/2;  //向上取整

快慢方式：

if (nums[mid]<target) l=mid+1; //L快
else r=mid;

if(nums[mid]>target) r=mid-1; //R快
else l=mid;

要注意这种方式必须先判断nums是否为空，否则会越界！return的部分要写在while外面！

后两种进化版相较于基本版有三点不同：

• 边界
• 快时取等，普通版是慢时取等if(nums[mid]<key) l=mid+1;
• 返回条件为不等式

下面看一下实例展示：

(1)求最小的i，使得a[i] = key，若不存在，则返回-1（下界）

int l =0,r=nums.size()-1;
while(l<r)
{
    int mid=(l+r)/2;
    if(nums[mid]<key) l=mid+1; //慢时取等
    else r=mid;
}
if(nums[r]==key) return r;
return -1;

(2)求最大的i，使得a[i] = key，若不存在，则返回-1（上界）

int l=0,r=nums.size()-1;
while(l<r)
{
    int mid=(l+r+1)/2;
    if(nums[mid]>key) r=mid-1;
    else l=mid;
}
if(nums[l]==target) return l;
return -1;

注意：下面这两种需要先判断边界，所谓的i只是指插入位置而已。

要快就要取等！这和前两种基本版是相反的。

(3)求最小的i，使得a[i] > key，若不存在，则返回-1（上界）

int l=0,r=nums.size()-1;
if(key>nums[r]) return r+1;
if(key<nums[l]) return l;
while(l<r)
{
    int mid=(l+r)/2;
    if(nums[mid]<=key) l=mid+1; //快时取等
    else r=mid;
}
if(nums[r]>key) return r;
return -1;

(4)求最大的i，使得a[i] < key，若不存在，则返回-1（下界）

int l=0,r=nums.size()-1;
if(key>nums[r]) return r;
if(key<nums[l]) return l-1;
while(l<r)
{
    int mid=(l+r+1)/2;
    if(nums[mid]>=target) r=mid-1;
    else l=mid;
}
if(nums[l]<target) return l;
return -1;

2. 寻找具体值

033 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2]，搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。你可以假设数组中不存在重复的元素。

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

解答：

基本模板是：最小i等于key。需要特别注意if(nums[mid]<target&&target<=nums[r])只有一个等，请参考模板if(nums[mid]<key) l=mid+1;这里也是没取等的，一定要注意！

另一个地方是else //mid左边是有序的 不要写成else if，因为相等的情况也需要包含进去。

另外如果nums[l]<=target这里去等了，则大if也要取等，比如：

if(nums[mid]>=nums[l]){
    if(nums[mid]>=target&&nums[l]<=target){
        r=mid;

int search(vector<int>& nums, int target) {
    if(nums.size()==0) return -1;
    int l=0,r=nums.size()-1;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(nums[mid]<nums[r])//mid右边是有序的
        { 
            //target在mid和r之间，只有一个等
            if(nums[mid]<target&&target<=nums[r])
                l=mid+1;
            else r=mid;
        } 
        else //mid左边是有序的
        {
            //target在l和mid之间，有两个等
            if(nums[l]<=target&&target<=nums[mid])
                r=mid;
            else l=mid+1;
        }
    }
    if(nums[r]==target) return r;
    return -1;
}

081 搜索旋转排序数组二

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。存在重复元素。

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

解答：

假设nums=[4,5,6,3,3,3,3]，target=4输入，可知mid为3，r也为3，又因为我们判断if(nums[mid]<nums[r])，所以认为左边是有序的，但[4,5,6,3]并不有序，所以结果错误，如果我们改为if(nums[mid]<=nums[r])就能正常输出。但如果输入数组变成nums=[4,4,4,4,1,2,3]则我们的改动又会出错。

所以，为了防止上述情况的出现，我们要斩掉两边重复的数字！我们只是去掉多余的重复，所以不需要斩尽杀绝，采用if(n[i]==n[i+1]) i++;而不是if(n[i]=n[i-1]) i++;

bool search(vector<int>& nums, int target) {
    if(nums.empty()) return false;
    int l=0,r=nums.size()-1;
    while(l<r)
    {
        while(l<r&&nums[l]==nums[l+1]) l++;
        while(l<r&&nums[r]==nums[r-1]) r--;
        int mid=(l+r)/2;
        if(nums[mid]<nums[r])
        {
            if(nums[mid]<target&&target<=nums[r])
                l=mid+1;
            else r=mid;
        }
        else{
            if(nums[l]<=target&&target<=nums[mid])
                r=mid;
            else l=mid+1;
        }
    }
    if(nums[r]==target) return true;
    return false;
}

074 搜索二维矩阵

判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

• 每行中的整数从左到右按升序排列。
• 每行的第一个整数大于前一行的最后一个整数。

输入:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
输出: true

解答：

两个二分搜索的组合，寻找一个最大的i，使得nums[i]<=key；再加一个常规的二分搜索。易错点在于：

• 需要判断边界
• col判断边界时要返回matrix.size()-1否则溢出
• if(matrix[l][0]<=target)和模板不一样，因为这里我们要找到nums[i]<=key

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0||matrix[0].size()==0) return false;
        int col=searchCol(matrix,target);
        if(col==-1) return false;
        int row=searchRow(matrix[col],target);
        if(row!=-1) return true;
        return false;
    }
    int searchCol(vector<vector<int>> matrix, int target){
        int m=matrix.size();
        if(matrix[0][0]>target) return -1;
        if(matrix[m-1][0]<target) return m-1;

        int l=0,r=m-1;
        while(l<r){
            int mid=(l+r+1)/2;
            if(matrix[mid][0]>target) r=mid-1;
            else l=mid;
        }
        if(matrix[l][0]<=target) return l;
        return -1;
    }
    int searchRow(vector<int> nums,int target){
        int l=0,r=nums.size()-1;
        while(l<r){
            int mid=(l+r)/2;
            if(nums[mid]<target) l=mid+1;
            else r=mid;
        }
        if(nums[r]==target) return r;
        else return -1;
    }
};

167 两数和—输入有序数组

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2

解答：

要注意这道题l=i+1而不是l=i，另外返回vector<int>{i+1,r+1};才符合题目要求。

vector<int> twoSum(vector<int>& numbers, int target) {
    if(numbers.empty()) return vector<int>{-1,-1};
    if(target<numbers[0]) return vector<int>{-1,-1};
    for(int i=0;i<numbers.size();i++)
    {
        int key = target-numbers[i];
        int l=i+1,r=numbers.size()-1;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(numbers[mid]<key) l=mid+1;
            else r=mid;
        }
        if(numbers[r]==key) return vector<int>{i+1,r+1};
    }
    return vector<int>{-1,-1};
}

2. 返回某个位置

034 在排序数组中查找元素的第一和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值，返回 [-1, -1]。

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

解答：

注意最后那里，不能写成if-else，否则会报错。

vector<int> searchRange(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    vector<int> res{ -1,-1 };
    if (nums.empty())
        return res;
    //search the min i
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (nums[mid] < target) l = mid + 1;
        else r = mid;
    }
    if (nums[r] == target) res[0] = r;
    else return res;
    //search the max i (Notice: reset l and r)
    l = 0, r = nums.size() - 1;
    while (l < r)
    {
        int mid = (l + r + 1) / 2;
        if (nums[mid] > target) r = mid - 1;
        else l = mid;
    }
    if (nums[l] == target) res[1] = l;
    return res; //不能写为if-else
}

035 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。

输入: [1,3,5,6], 5
输出: 2
输入: [1,3,5,6], 2
输出: 1

解答：

翻译过来就是：找到最小的i，使得a[i] >= key。这种类型需要改动最后return的判断，以及之前需要加上边界判断。

int searchInsert(vector<int>& nums, int target) {
    int l=0,r=nums.size()-1;
    if(nums.size()==0) return 0;
    if(nums[r]<target) return r+1;
    if(nums[l]>target) return l;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(nums[mid]<=target) l=mid+1;
        else r=mid;
    }
    if(nums[r]>=target) return r;
    return -1;
}

069 X的平方根

实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。

输入: 8
输出: 2
说明: 8 的平方根是 2.82842..., 
     由于返回类型是整数，小数部分将被舍去。

解答：

需要变通一下：将x视为target，将mid*mid视为nums[mid]。这样就变为了：找最大的i使得的a[i]<key

int mySqrt(int x) {
    long l=0,r=50000;
    while(l<r){
        long mid=(l+r+1)/2;
        if(mid*mid==x) return mid;
        if(mid*mid>x) r=mid-1;
        else l=mid;
    }
    return l;
}

3. 未知具体值

153 寻找旋转数组最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。找到那个旋转点

输入: [3,4,5,1,2]
输出: 1
输入: [4,5,6,7,0,1,2]
输出: 0

解答：

基本思路就是如果nums[mid] > nums[r]则最小值在右边，l往上提，反之r往下拉。由于预设的是所以l=mid+1，最后返回r（其实最后l==r，返回哪一个都一样）

int findMin(vector<int>& nums) {
    int l = 0, r = nums.size() - 1;
    while (l < r)
    {
        int mid = (l + r) /2;
        //assume that 
        //there is no dumplicated elements
        if (nums[mid] > nums[r])
            l = mid + 1;
        else 
            r = mid ;
    }
    return nums[l];
}

162 寻找峰值

峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，其中 nums[i] != nums[i+1]，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5 
解释: 你的函数可以返回索引 1，其峰值元素为 2；

解答：

int findPeakElement(vector<int>& nums) {
    int l = 0, r = nums.size() - 1;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        //如果mid<mid+1，峰肯定在右边
        if (nums[mid] < nums[mid + 1])
            l = mid + 1;
        else
            r = mid;
    }
    return r;
}