问题出处

相信很多小伙伴在刷算法题时总是会发现我们的代码超时，看到问题不是很难，心想so easy嘛这不是， 上来直接暴力题解，结果运行时结果显示超出时间限制。相信来找二分的你，应该也是碰到这种问题，并且对二分了解的不是很清楚，所以接下来让我们一起学习和回顾二分查找算法吧。

二分查找简介

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

分查找原理

1. 首先，如果我们有一个递增的数组表-即按升序排列，然后设置搜索区间，定义搜索区间的左右边界，然后循环压缩搜索区间，中间值 mid = (left + (right - left)) / 2. 这样设置mid的好处可以防止当（left + right）太大时可能超出int类型的最大接受范围，防止溢出。
2. 然后比较target目标值和中间值的大小： 如果 target < nums[mid]，就在右区间搜索,right = mid - 1. 如果 target > nums[mid], 就在左区间搜索,left = mid + 1. 相等就直接返回mid值，即找到target值。

下面是这个过程的代码模板（c++为例）：

      int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if(target < nums[mid]){
                right = mid - 1;  //明确 mid 下标的值大于target 所以右边界下标为 mid - 1
            }
            else if(target > nums[mid]){
                left = mid + 1; //明确 mid 下标的值小于target 所以左边界下标为 mid + 1
            }
            else {
                return mid;
            }
        }
        return -1;
    }

这个代码的前提是 right = nums.size() - 1,使得搜索区间为左闭右闭[left , right], 这样在while循环内使得left 可以等于 right，因为我们的right是可取的。

当我们定义右边界 right = nums.size() 时，我们的代码就有点小改动，因为搜索区间变为了左闭右开[left , right)。

代码如下：

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

此处的while循环就少了一个left = right ,因为left 本来就不可能去等于right ，就好比只有一个单个元素的数组 [1) ，这个左边界1肯定不能等于右边界的1，因为有边界本来就取不到值。所以循环内的结束条件还是取决于我们的区间如何定义，这样代码也需要有稍加改动。

以上就是二分的全部内容了，希望能给正在学算法的你带来一点小小帮助，觉得写的不错可以点赞支持一下哦！

总结

其实在刚开始刷算法题时，作为新手的我们在想题解的时候，总是会想着暴力解题，其实除了暴力还有很多的解题方式和方法技巧等，随着我们更加深入的了解，对于算法我们一定能练的炉火纯青。