二分搜索

ref
LeetCode Binary Search Summary 二分搜索法小结
july编程之法-第四章 查找匹配

二分查找法作为一种常见的查找方法，将原本是线性时间提升到了对数时间范围，大大缩短了搜索时间，具有很大的应用场景，经常在对于有序／部分有序容器的搜索应用到。

基本思想

它的基本思想是把有序的数组从中间分为两部分，和中值比较后每次抛却一半的数，在剩下的一半中搜索。

1. 一开始，范围覆盖整个数组。
2. 将数组的中间项与T进行比较，如果T比数组的中间项要小，则到数组的前半部分继续查找，反之，则到数组的后半部分继续查找。
3. 如此，每次查找可以排除一半元素，范围缩小一半。就这样反复比较，反复缩小范围，最终就会在数组中找到T，或者确定原以为T所在的范围实际为空。

此时，可能有不少读者心里嘀咕，不就二分查找么，太简单了。然《编程珠玑》的作者Jon Bentley曾在贝尔实验室做过一个实验，即给一些专业的程序员几个小时的时间，用任何一种语言编写二分查找程序（写出高级伪代码也可以），结果参与编写的一百多人中：90%的程序员写的程序中有bug（我并不认为没有bug的代码就正确）。
也就是说：在足够的时间内，只有大约10%的专业程序员可以把这个小程序写对。但写不对这个小程序的还不止这些人：而且高德纳在《计算机程序设计的艺术 第3卷 排序和查找》第6.2.1节的“历史与参考文献”部分指出，虽然早在1946年就有人将二分查找的方法公诸于世，但直到1962年才有人写出没有bug的二分查找程序。

实现要点

要准确实现二分查找，首先要把握下面几个要点：

• 关于right的赋值
  right = n-1 => while(left <= right) => right = middle-1;
  right = n => while(left < right) => right = middle;
• middle的计算不能写在while循环外，否则无法得到更新。

基本二分搜索可以写成非递归和递归形式：
递归写法：

int binarySearchRecursive(vector<int>& nums, int target, int left, int right){
    if (left > right) return -1;
    int mid = (left + right) / 2;
    if (nums[mid] < target){
        return binarySearchRecursive(nums, target, mid + 1, right);
    }
    else if (a[mid] > x){
        return binarySearchRecursive(nums,target left, mid - 1);
    }
    else{
        return mid;
    }
}

非递归写法见下文。

时间空间复杂度：对于包含N个元素的表，整个查找过程大约要经过log(2)N次比较。

二分查找的基本思想是将n个元素分成大致相等的两部分，去a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果xa[n/2],则只要在数组a的右半部搜索x.时间复杂度无非就是while循环的次数！

总共有n个元素，每次循环过后，剩余查找范围为n,n/2,n/4,....n/2^k，其中k就是循环的次数, 循环退出的条件查找范围里只剩下一个数，即n/2^k=1,可得k=log2n,所以时间复杂度可以表示为O(logN)

二分搜索例题分析

二分搜索题目可以分为以下四类

第一类： 基本型： 需查找和目标值完全相等的数

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

注意二分查找法的写法并不唯一，主要可以变动地方有四处：
第一处是right的初始化，可以写成 nums.size() 或者 nums.size() - 1
第二处是left和right的关系，可以写成 left < right 或者 left <= right
第三处是更新right的赋值，可以写成 right = mid 或者 right = mid - 1
第四处是最后返回值，可以返回left，right，或right - 1

但是这些不同的写法并不能随机的组合，
若right初始化为了nums.size()，那么就必须用left < right，而最后的right的赋值必须用 right = mid。但是如果我们right初始化为 nums.size() - 1，那么就必须用 left <= right，并且right的赋值要写成 right = mid - 1，不然就会出错。所以博主的建议是选择一套自己喜欢的写法，并且记住，实在不行就带简单的例子来一步一步执行，确定正确的写法也行。

第二类： 查找第一个不小于目标值的数，可变形为查找最后一个小于目标值的数

要查找的目标值不一定会在数组中出现，也有可能是跟目标值相等的数在数组中并不唯一，而是有多个，那么这种情况下nums[mid] == target这条判断语句就没有必要存在。比如在数组[2, 4, 5, 6, 9]中查找数字3，就会返回数字4的位置；在数组[0, 1, 1, 1, 1]中查找数字1，就会返回第一个数字1的位置。我们可以使用如下代码：

在C++的STL中有专门的查找第一个不小于目标值的数的函数lower_bound

第三类： 查找第一个大于目标值的数，可变形为查找最后一个不大于目标值的数

在C++的STL也有专门的函数upper_bound，这里跟上面的那种情况的写法上很相似，只需要添加一个等号，将之前的 nums[mid] < target 变成 nums[mid] <= target，就这一个小小的变化，其实直接就改变了搜索的方向

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

第四类： 用子函数当作判断关系

在二分查找法重要的比较大小的地方使用到了子函数，并不是之前三类中简单的数字大小的比较.

例题：

33. 搜索旋转排序数组(属于第4类)

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

思路：

• 在有序数组里二分搜索的时间复杂度是O（logn），
  本题关键是如何将有序数组里二分搜索迁移到这个特殊数组中来。
• 观察这个数组，其中任意一个数，或者它前面序列为升序，或者它后面序列为升序。前后总有1个（或2个）序列为升序。利用这点来查找target。
• 有了这个思路之后，还要注意一些重要的细节（大于？还是大于等于；特殊情况等）

详细解说关键步骤：

• 第一步：给出搜索范围的两个标志left =0 ;right = len-1; 计算mid = left+(right-left)/2;
• 第二步：比较nums[mid]和target的大小，如果等于返回结果mid；否则进行第三步；
• 第三步：判断此mid前后序列，哪个是升序，哪个是混序；
  比较nums[left]和nums[mid]，如果nums[left]<= nums[mid]则前面为纯升序跳到步骤四，否则后面为纯升序调到步骤五。
• 第四步：此时，mid前为纯升序，如果target是在left和mid之间的数，则right范围缩小到mid-1;否则，left的范围缩小到mid+1;此轮计算完毕，重新计算mid值，进行下一轮。
• 第五步：此时,mid后为纯升序，如果target是在mid和right之间的数，则left范围缩小到mid+1;否则，right范围缩小到mid-1;此轮计算完毕，重新计算mid值，进行下一轮。
• 第六步：如此循环，直到找到这个target或者left==right停止搜索返回没有找到这个数。

例如：4，5，1，2，3 target=5
** left(nums[left]) ; right(nums[right]) ; mid(nums[mid])
- 0(4) ; 4(3) ; 2(1);第一轮
- 1!=5,no return;
- 4>1,go to step5;
- 5 is not in 1-3, right=mid-1=1,第二轮
- 0(4);1(5);0(4);
- 4!=5,no return;
- 4<=4,go to 4;
- 5 is not in 4, left = mid+1 = 1,第三轮
- 1(5),1(5);1(5);
- 5=5, 命中return mid = 1;

代码如下：

class Solution {
  public:
    int search(vector<int> &nums, int target) {
        if (nums.size() == 0) return -1;
        auto low = nums.begin(), high = nums.end() - 1;
        while (low <= high) {
            auto mid = low + (high - low) / 2;
            if (*mid == target) return mid - nums.begin();
            if (*mid >= *low) {
                if (*low <= target && target < *mid) high = mid - 1;
                else low = mid + 1;
            } else {
                if (*low > target && target > *mid) low = mid + 1;
                else high = mid - 1;
            }
        }
        return -1;
    }
};