欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找的细节

程序员文章站 2024-03-20 17:15:10
...


二分查找原理很简单,就是在一个已经排好序(或者分段排好序)的数组中用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;
};