本节博客详述“二分查找”并且以例子来进行讨论，有需要借鉴即可。

1.二分查找

1.1使用前提

使用的条件：数组具有“二段性”，二段性指的是数组可以根据某一规律分为两组，且在干掉一半之后仍可以对另一半进行复用相同的规律。

1.2模板

二分查找的代码具有高度统一性，因而可以套用模板，但这并不意味着自己不需要用脑子无脑套模板。

一般二分查找模板、查找左边界二分模板、查找右边界二分模板。

下面是通过一道具体的题目来介绍二分查找算法的由来。

2.题目

题目链接：LINK

首先肯定是暴力解法，挨个遍历就行了，找到了返回对应的下标，找不到返回-1

但是这个暴力解法有点慢，慢就慢在一次只能干掉一个数字。

有序数组满足“二段性”，这里的“二段性”就是以某个数字作比较，可以将数组分为比这个数字大的一组和小的一组，因而可以利用有序的特点直接上二分查找算法。

思考：结束条件是什么？
答：left <= right，这个等于一定要注意，因为一个数字也要判断一下。
不然会出下以下“悲剧”：

思考：为什么一定得二分，而不是三分、四分…N分?
答：这里推一篇文章，有兴趣可以看一下：LINK

二分查找复杂度
答：logN

3.题解代码示例

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        //一般情况
        for(int left = 0,right = nums.size() - 1,mid; left <= right;)
        {
            //mid = (left + right) / 2;
            mid = left + (right - left) / 2;//优化，防止两数相加溢出问题
            if(nums[mid] > target)right = mid - 1;
            else if(nums[mid] < target)left = left + 1;
            else return mid;
        }

        return -1;
    }
};

4.二分查找的一般模板

while(left < right)
{
int mid = left + (right - left) / 2;
if(...)
//
else if(...)
//
else
return ...
}

5.总结

我感觉二分查找大部分人是比较熟悉的，这里需要注意两个点，为什么是二分？二分查找的使用前提一定是有序吗？

题目太简单，不多说。

---

EOF