一、二分查找介绍

首先使用二分法的前提是这个数组或者序列是排好序的。对于一个排好序的数组（升序），如果要让我们从中找一个指定的数并输出它的下标，我们可以直接暴力枚举，时间复杂度为O(n),当我们使用二分查找的时候它的时间复杂度为O(log n)

二分法的核心思想就是：每次都将查询的范围缩小一半

还是上面的例子，我们首先选择数组中间的数字和目标值进行比较，那么会有三种结果

1.相等：这种情况最好了可以直接返回答案

2.比目标值大：因为我们的数组是排好序的，那么中间的值比它大，是不是就说明目标值在它的左边，所以我们的下一步就是往左边接着二分

3.比目标值小：同理，不同点在于这次我们要往右边接着二分

代码实现：

#include<bits/stdc++.h>
using namespace std;
int main()

{
    vector<int> v = {1,5,6,8,10,82,699};
    int l = 0, r = v.size() - 1;
    int target = 5;
    while(l  < r){
        int mid = (l + r) / 2;//不用纠结数组的长度是奇数还是偶数
        if(v[mid] == target){
            cout << mid;
            break;
        }
        else if(v[mid] > target)
            r = mid;//这样查询的右边界就到了mid这里
        else
            l = mid;
    }
    
    return 0;
}

上面只是简单实现了一下，是不严谨的，但是有一点数组的长度是奇数还是偶数真的不重要！！！

二、边界

二分查找的思想是很好理解的，难的是边界的考虑。也就是上面代码中是 l < r 还是 l <= r，以及是 r = mid 还是 r = mid - 1

一般的来说有以下几种

1.左开右闭（比较少见）

2.左闭右开

3.左闭右闭

还是上面的例子，这次我们分析一下，当left == right的时候是有没有意义的以及right = ?

首先我们要确定查找的区间是什么，我们发现目标值target是在[left , right]这个区间当中的,所以当left == right的时候，它在数组中所对应的值也有可能是我们要找的值，即有意义。

然后就是right的取值，我们的判断条件是if(v[mid] > target),想一下当这个条件成立的时候是不是就说明mid所对应的值是比target大的，所以我们不需要再让right = mid而是让right = mid - 1

综上优化后的代码是：

#include<bits/stdc++.h>
using namespace std;
int main()

{
    vector<int> v = {1,5,6,8,10,82,699};
    int left = 0, right = v.size() - 1;
    int target = 5;
    while(left <= right){
        int mid = (left + right) / 2;
        if(v[mid] > target)
            right = mid - 1;
        else if(v[mid] < target)
            left = mid + 1;//它和right同理，只不过它是要往前走一位
        else{
            cout << mid;//找到直接输出并return
            return 0;
        }
    }
    cout << -1;//没找到就输出-1
    return 0;
}

接下来我们来看左闭右开即[left,right)，首先很容易想到的是left == right是没有意义的，然后就是right的取值变化，假设right = mid - 1,根据区间的定义

right是取不到的，所以mid - 1是取不到的，再看判断条件是if(v[mid] > target)这就说明mid也是取不到的，如果right = mid - 1就相当于一次去掉了两个数，这显然是不对的，因为mid - 1在数组中所对应的值有可能是目标值，不能去掉。

代码实现：

#include<bits/stdc++.h>
using namespace std;
int main()

{
    vector<int> v = {-1,0,1,5,6,8,10,82,699};
    int left = 0, right = v.size() - 1;
    int target = 8;
    while(left < right){
        int mid = (left + right) / 2;
        if(v[mid] > target)
            right = mid;
        else if(v[mid] < target)
            left = mid + 1;//left还是加1，因为左区间是能取到的
        else{
            cout << mid;//找到直接输出并return
            return 0;
        }
    }
    cout << -1;//没找到就输出-1
    return 0;
}