二分查找总结与实践

2022/04/27

刷完Leetcode二分查找专题的总结

1. 几个基本的二分查找函数

一些基础的二分查找函数的实现，包括查找target应的index，查找小于或者target的index，和大于等于target的index

/*
要求data为已经排好序的int数组
如果target存在于data中则返回其在data中所对应的index，如果不存在则返回-1
*/
int search(vector<int>& data, int target){
    int left = 0;
    int right = data.size() - 1;
    while(left <= right){
        int mid = (left+right)/2;
        if(data[mid] == target){
            return mid;
        }else if(data[mid] < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return -1;
}

这个应该是最简单的二分查找函数了，不过注意为什么while的判断条件要是left <= right, 如果是小于就会计算错误。假设输入的数组为{1, 2, 3, 4, 5, 6, 7}，target为1，二分查找的过程应该是这样的

left = 0, right = 6, mid = 3, data[mid] = 4
left = 0, right = 2, mid = 1, data[mid] = 2
left = 0, right = 0, mid = 0, data[mid] = 1

如果判断条件是小于的话，就无法进行第三次循环，也就找不到target返回-1了，也就是说如果用小于作为判断条件的话就会忽略target在left或者right上这种情况，这样就可能会得出错误的值。

1. 2 notGreater

如果target存在的话返回target所对应的下标，如果不存在则返回于target在数值上最相近且小于target值的下标，就相当于STL中的lower_bound函数

/*
要求data为已经排好序的int数组
如果`target`存在的话返回`target`所对应的下标，如果不存在则返回于`target`在数值上最相近且小于`target`值的下标
*/
int notGreater(vector<int>& data, int target){
    int left = 0;
    int right = data.size() - 1;
    while(left <= right){
        int mid = (left+right)/2;
        if(data[mid] == target){
            return mid;
        }else if(data[mid] < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return right;
}

和之前的search函数只有最后一行不同，search中如果找不到target则返回-1，这里则是返回right，因为上面的判断条件是left <= right所以退出while循环的时候一定有right < left，并且如果target存在的话退出循环的时候应该正好是target所在的位置，所以找不到返回right就可以了。

1.3 notLower

如果target存在的话返回target所对应的下标，如果不存在则返回于target在数值上最相近且大于target值的下标

/*
要求data为已经排好序的int数组
如果`target`存在的话返回`target`所对应的下标，如果不存在则返回于`target`在数值上最相近且大于`target`值的下标
*/
int notLower(vector<int>& data, int target){
    int left = 0;
    int right = data.size() - 1;
    while(left <= right){
        int mid = (left+right)/2;
        if(data[mid] == target){
            return mid;
        }else if(data[mid] < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return left;
}

和上面的那个notGreater正好是相反的情况就不做过多解释了。

1.3 带有重复元素的二分查找

假设给定一个递增的数组nums，里面可能存在重复元素，要求返回第一次出现target的下标。

解决思路很简单，当nums[mid] == target的时候，left或right都向左移一个单位即可。下面是完整代码

/*
要求data为已经排好序的int数组
如果target存在于data中则返回其在data中所对应的index，如果不存在则返回-1
*/
int search(vector<int>& data, int target){
    int left = 0;
    int right = data.size() - 1;
    while(left <= right){
        int mid = (left+right)/2;
        if(data[mid] == target){
            right--;
        }else if(data[mid] < target){
            left = mid + 1;
        }else{
            right = mid - 1;
        }
    }
    return -1;
}

2. 二分查找实践

在Leetcode上面刷到的一些比较有意思的二分查找题

154. Find Minimum in Rotated Sorted Array II

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

  • [4,5,6,7,0,1,4] if it was rotated 4 times.
  • [0,1,4,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [1,3,5]
Output: 1

Example 2:

Input: nums = [2,2,2,0,1]
Output: 0

Constraints:

  • n == nums.length
  • 1 <= n <= 5000
  • -5000 <= nums[i] <= 5000
  • nums is sorted and rotated between 1 and n times.

Follow up: This problem is similar to Find Minimum in Rotated Sorted Array, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int left = 0;
        int right = numbers.size() - 1;
        while (left <= right) {
            int mid = (left+right)/ 2;
            if (numbers[mid] < numbers[right]){     // 将右边的舍弃
                right = mid;
            }else if (numbers[mid] > numbers[right]) {      // 将左边的舍弃
                left = mid + 1;
            }else {
                right -= 1;
            }
        }
        return numbers[left];
    }
};

这题有意思的点在于在进行二分查找的时候并没有一个具体固定的target， 这里选取查找区间的最右边那个点的值作为target，因为在包含目标值的区间中 $ right left$。 如果mid要比target大的话就将左边的那一部分丢掉，如果mid要比target小则把右边那一部分丢掉，因为可能含有重复元素，所以如果遇到mid与target相等时就使用上面提到的带有重复元素的二分查找方法。