二分查找的细节

二分查找的细节

• 二分法模板
• 例题

二分查找原理很简单，就是在一个已经排好序(或者分段排好序)的数组中用O(logn)的时间复杂度找到目标值，如果没有，则返回目标值应该被插入的位置下标。刷题的时候踩了个坑，mark一下：

二分法模板

当mid是用(left + right) >> 1的算法计算(也就是奇数序列mid会在中间，偶数序列mid会在偏左边的位置)，并且把nums[mid] >= target的情况合并起来，那么二分查找可以归结为"找左边"，即无论target在不在目标数组里，最后只要最后返回left指针就是答案，试讨论这种情况下"找左边"的合理性:

下面列出了二分查找的四种终止情况：

1. 奇数子序列中找到target:
   例如[...,6,7,8,...]中找7,此时left指向6，right指向8，那么mid指向7，那么nums[mid] === 7，让right = mid - 1。
   下一次循环的时候left指向6，right指向7，mid指向6，那么nums[mid] < 7，让left = mid + 1；
   下一次循环的时候left指向7，right指向7，mid指向7，那么nums[mid] === 7，让right = mid - 1;
   最后，由于left(7) > right(6)，循环终止，返回left即7的位置；
2. 奇数子序列中找不到target:
   例如[...,6,8,9,...]中找7,此时left指向6，right指向9，mid指向8，那么nums[mid] > 7，让left = mid + 1。下一次循环的时候不满足left <= right的条件，推出循环，返回left即7应该被插入的位置；
3. 偶数子序列中找到target：
   例如[…7,8…]中找7，此时left指向7，right指向8，mid指向7，那么nums[mid] === 7，让right = mid - 1。
   下一轮循环的时候，left指向7,right指向7，mid指向7，那么nums[mid] === 7，让right = mid - 1。
   最后，由于left(7) > right(6)，循环终止，返回left即7的位置；
4. 偶数子序列中找不到target：
   例如[…6,8…]中找7，此时left指向6，right指向8，mid指向6，那么nums[mid] < 7，让left = mid + 1；
   下一轮循环的时候，left指向8，right指向8，mid指向8，那么nums[mid] > 7，让right = mid - 1。
   下一轮循环的时候，由于left(8) > right(6)，循环终止，返回left即7应该被插入的位置；

综上，二分查的实现可以写成下面这个形式：

function findTarget(nums, target){
	if(nums.length <= 1) return nums[0] === target ? 0 : -1;
	let left = 0, right = nums.length - 1; // 目标数组的首尾
	while(left <= right){
		let mid = (left + right) >> 1; // mid中点
		if(nums[mid] < target) left = mid + 1; // 找右边
		else right = mid - 1; // 找左边
	}
	return left; // 统一返回left
}

例题

LeetCode35 搜索插入位置

LeetCode35 搜索插入位置
这道题就是纯粹的二分查找

LeetCode34 在排序数组中查找元素的第一个和最后一个位置

LeetCode34 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

这道题就可以用二分法的模板。查找target的区间其实就是在找target出现的第一个位置(如果不存在那么就返回target应该出现的第一个位置)，和target + 1出现的第一个位置(如果不存在那么就返回target + 1应该出现的第一个位置)；

当然，这道题要求如果没有出现target返回[-1,-1]，所以最后需要判断一下；

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function findTarget(nums, target){
    if(nums.length <= 1) return nums[0] === target ? 0 : -1;
    let left = 0, right = nums.length - 1; // 目标数组的首尾
    while(left <= right){
        let mid = (left + right) >> 1; // mid中点
        if(nums[mid] < target) left = mid + 1; // 找右边
        else right = mid - 1; // 找左边
    }
    return left; // 统一返回left
}

var searchRange = function(nums, target) {
    if(nums.length <= 1) return [target === nums[0] ? 0 : -1, target === nums[0] ? 0 : -1];
    res = [-1,-1];
    const leftBound = findTarget(nums, target);
    const rightBound = findTarget(nums,target + 1) - 1;
    if(leftBound < nums.length && nums[leftBound] === target && rightBound < nums.length && nums[rightBound] === target){
        res = [leftBound, rightBound];
    }
    return res;
};