Mute

个人技术博客

0%

二分查找

发表于 分类于

最近陆陆续续做了一些题，越发能体会到：思路很简单，细节是魔鬼。

关于细节，主要就体现在mid到底是加一还是减一，while里面应该用 <= 还是 < 。

一个笑话：

有一天小明到图书馆借了 N 本书，出图书馆的时候，警报响了，于是保安把小明拦下，要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下，以找出引发警报的书，但是保安露出不屑的眼神：你连二分查找都不会吗？于是保安把书分成两堆，让第一堆过一下报警器，报警器响；于是再把这堆书分成两堆…… 最终，检测了 logN 次之后，保安成功的找到了那本引起警报的书，露出了得意和嘲讽的笑容。于是小明背着剩下的书走了。

从此，图书馆丢了 N - 1 本书。

简介：

二分查找（binary search），也称折半搜索、对数搜索，是用来在一个有序数组中查找某一元素的算法。

以在一个升序数组中查找一个数为例。

它每次考察数组当前部分的中间元素，如果中间元素刚好是要找的，就结束搜索过程；如果中间元素小于所查找的值，那么左侧的只会更小，不会有所查找的元素，只需到右侧查找；如果中间元素大于所查找的值同理，只需到左侧查找。

时间复杂度：O(logN)

常见的应用场景：

查找一个数、查找左侧边界、查找右侧边界。

二分查找基本框架：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(vector<int>& nums, int target){
    int left = 0, right = ...;
    while(...){
        int mid = left + (right - left) >> 1; //同理(left + right) / 2 
        if(nums[mid] == target){			//可以防止数据太大直接相加导致数据溢出
            ...;
        }else if(nums[mid] < target){        // ...标记的地方就是要注意细节的地方
            left = ...;
        }else if(nums[mid] > target){
            right =...;
        }
    }
    return ...;
}

最基本的二分查找：

1
2
3
4
5
6
初始化 right = nums.size() - 1 
while(left <= right) //终止条件为left == right + 1，此时区间[right+1, right]为空。
    left = mid+1，right = mid-1; // target == nums[mid]直接返回

while(left < right) //终止条件为left == right，此时区间[left, left]非空，还有一个被漏掉的数据需要处理。
    nums[left] == target ? left : -1;

寻找左侧边界：

对于寻找左右边界的二分查找，常见的手法是使用左闭右开的搜索区间。

1
2
3
4
5
6
7
初始化 right = nums.length
while (left < right) //搜索区间是 [left, right)
	left = mid + 1 和 right = mid  
    
    //因为我们需找到 target 的最左侧索引
	//所以当 nums[mid] == target 时不要立即返回
	//而要收紧右侧边界以锁定左侧边界

寻找右侧边界：

1
2
3
4
5
6
7
初始化 right = nums.length
 while (left < right) //搜索区间是 [left, right)
	 left = mid 和 right = mid - 1

//因为我们需找到 target 的最右侧索引
//所以当 nums[mid] == target 时不要立即返回
//而要收紧左侧边界以锁定右侧边界