二分查找模板分析 & LeetCode34 在排序数组中查找元素的第一个和最后一个位置

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

题目
解题
- 解题一：二分查找版本一
- 解题二：二分查找版本二
- 解题三：二分查找版本三
- 解题四

题目

解题

二分查找也称折半查找（Binary Search），是一种在有序数组中查找某一特定元素的搜索算法。我们可以从定义可知，运用二分搜索的前提是数组必须是有序的，这里需要注意的是，我们的输入不一定是数组，也可以是数组中某一区间的起始位置和终止位置。

解题一：二分查找版本一

代码来自两次二分查找（Java）
官方解答在排序数组中查找元素的第一个和最后一个位置的视频题解讲解的是这个代码

因为二分查找有许多版本，所以先来看看这一版的模板，参考的是图解二分 | 最清晰易懂的讲解 | 一次性帮你解决二分边界问题【c++/java版本】

为了避免溢出，mid 的计算最好写成 m i d = l + ( r − l ) / 2 mid = l + (r-l)/2 mid=l+(r−l)/2 或者 m i d = l + ( r − l ) > > 1 mid = l + (r-l)>>1 mid=l+(r−l)>>1

为了避免溢出，mid 的计算最好写成 m i d = l + ( r − l + 1 ) / 2 mid = l + (r-l+1)/2 mid=l+(r−l+1)/2 或者 m i d = l + ( r − l + 1 ) > > 1 mid = l + (r-l+1)>>1 mid=l+(r−l+1)>>1

上段文字解释了为什么两个模板 mid 取值不同，因为 l l l 和 1 1 1 长得很像，所以要不仔细辨认的话，估计会看懵。

有一点我和文章中想的不一样，出循环的情况应该是 left = right，但此时这个索引对应的下标还没有判断过，所以要对left对应的值单独判断。

循环条件是 while (left < right) 而非 while (left <= right) 的原因是：如果 left = right, mid = left, 在模板一中 mid 有可能成为新的右边界，在模板二中 mid 有可能成为新的左边界，如此便会进入无限循环。

注释里讲明了每一步的书写根据。

// javascript
var searchRange = function(nums, target) {
    if (nums.length === 0) return [-1, -1];
    const firstPosition = findFirstPosition(nums, target);
    // -1 代表 nums 里没有 target 
    if (firstPosition === -1) return [-1, -1];
    // findLastPosition 被调用代表 nums 里有 target
    const lastPosition = findLastPosition(nums, target);
    // 返回找到的值
    return [firstPosition, lastPosition];
};

const findFirstPosition = (nums, target) => {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        // 下一轮搜索区间是 [left..mid] / [mid + 1..right] 符合模板一
        const mid = left + ((right - left) >> 1);
        // 小于一定不是解
        if (nums[mid] < target) {
            // 下一轮搜索区间是 [mid + 1..right]
            left = mid + 1;
        } else {
            // nums[mid] = target, 下一轮搜索区间是 [left..mid]
            // nums[mid] > target, 下一轮搜索区间是 [left..mid - 1]
            // 合并取成 [left..mid] 符合模板一
            right = mid;
        }
    }
    // left = right, nums[left] 还没有被判断过
    // 如果 nums[left] = target, 它就是 target 出现的第一个位置
    if (nums[left] === target) return left;
    // 否则返回 -1, 代表的是没有找到
    return -1;
};

const findLastPosition = (nums, target) => {
    let left = 0, right = nums.length - 1;
    while (left < right) {
        // 下一轮搜索区间是 [left..mid - 1] / [mid..right] 符合模板二
        const mid = left + ((right - left + 1) >> 1);
        if (nums[mid] > target) {
            // 下一轮搜索区间是 [left..mid - 1]
            right = mid - 1;
        } else {
            // nums[mid] = target, 下一轮搜索区间是 [mid..right]
            // nums[mid] < target, 下一轮搜索区间是 [mid + 1..right]
            // 合并取成 [mid..right] 符合模板二
            left = mid;
        } 
    }
    // findLastPosition 被调用代表 nums 里有 target, 所以 left 对应的值一定是 target
    // 如果想进行判断也可以, 但没必要
    return left;
};

解题二：二分查找版本二

代码来自：【动画模拟】一文带你搞定二分查找及其多个变种里面总结了一波【二分查找】的题目，建议一起刷来感受一下二分查找的解题思路。

刚刚有解释上面两个模板 while 循环里不能加等于的原因，现在上模板三，可以加等于是因为下一次搜索区间为 [left, mid - 1] 或 [mid + 1, right]，mid 会被排除在外。

模板三的优秀之处在于当 left = right 时，还可以进循环，不用额外判断。

计算 first position 时，当 target = nums[mid] 时，right = mid -1，最后返回 left。left 代表的是 target 出现的第一个位置，或者应该被插入的位置（target 可能不在 nums 里）；

计算 last position 时，当 target = nums[mid] 时，left = mid + 1，最后返回 right。right 代表的是 target 出现的最后一个位置，或者应该被插入的前一个位置（target 可能不在 nums 里）。刚好和计算 first position 时条件相反

所以就需要两个函数来进行操作。

// javascript
var searchRange = function(nums, target) {
    const lower = findFirstPosition(nums, target);
    const upper = findLastPosition(nums, target);
    // target 不存在情况
    if (upper < lower) {
        return [-1, -1];
    }
    return [lower, upper];
};

const findFirstPosition = (nums, target) => {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        const mid = left + ((right - left) >> 1);
        // 当 nums[mid] = target 时，因为要找 target 出现的第一个位置，继续往前找
        if (nums[mid] >= target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // 返回的是 left
    return left;
};

const findLastPosition = (nums, target) => {
    let left = 0, right = nums.length - 1;
    while (left <= right) {
        const mid = left + ((right - left) >> 1);
        // 当 nums[mid] = target 时，因为要找 target 出现的最后一个位置，继续往后找
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1; 
        }
    }
    // 返回的是 right
    return right;
};

拿几个用例测试一下：

nums = [1,3,5,6], target = 5

函数	变量值
findFirstPosition	left = 2, right = 1
findLastPosition	left = 3, right = 2
searchRange	lower = 2, upper = 2

nums = [1,3,5,5,6], target = 5

函数	变量值
findFirstPosition	left = 2, right = 1
findLastPosition	left = 4, right = 3
searchRange	lower = 2, upper = 3

nums = [1,3,5,6], target = 2

函数	变量值
findFirstPosition	left = 1, right = 0
findLastPosition	left = 1, right = 0
searchRange	lower = 1, upper = 0

nums = [1,3,5,6], target = 7

函数	变量值
findFirstPosition	left = 4, right = 3
findLastPosition	left = 4, right = 3
searchRange	lower = 4, upper = 3

nums = [1,3,5,6], target = 0

函数	变量值
findFirstPosition	left = 0, right = -1
findLastPosition	left = 0, right = -1
searchRange	lower = 0, upper = -1

解题三：二分查找版本三

最厉害的一步就是将找 rightIdx 变成寻找第一个大于 target 的下标 - 1，如此一来找第一个和最后一个 target 的逻辑就不是相反的啦，于是乎可以用一个函数解决啦！

有几个重点：

更新 ans 的判断条件
添加 lower 函数，让 binarySearch 变得可被复用
binarySearch 中 ans 初始化为 nums.length

var searchRange = function(nums, target) {
    let ans = [-1, -1];
    const leftIdx = binarySearch(nums, target, true);
    const rightIdx = binarySearch(nums, target, false) - 1;
    if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] === target && nums[rightIdx] === target) 
    {
        ans = [leftIdx, rightIdx];
    }
    return ans;
};

// 如果找不到，ans = nums.length
// 如果找得到，ans < nums.length
const binarySearch = (nums, target, lower) => {
    let left = 0, right = nums.length - 1, ans = nums.length;
    while (left <= right) {
        const mid = left + ((right - left) >> 1);
        // 因为 mid 已经比较过，所以下一次循环要排除掉 mid
        // 如果lower是false，当前元素 > target，更前的 > target的元素在mid左边
        // 如果lower是true，当前元素 >= target，更前的 >= target的元素在mid左边
        if (nums[mid] > target || (lower && nums[mid] >= target)) {
            ans = mid;           // 记录mid
            right = mid - 1;
        } 
        // 如果lower是false，当前元素 <= target，左边的元素均 <= target
        // 如果lower是true，当前元素 < target，左边的元素均 < target
        else {
            left = mid + 1;
        }
    }
    // 也可以不用 ans，直接 return left；
    return ans;
};

leftIdx 是数组中第一个大于等于 target 的元素下标，rightIdx 是数组中第一个大于 target 的元素下标。有几种特殊情况，这里验证一下：

nums 所有元素均小于 target，例如 [1, 2, 3], target = 4，leftIdx = nums.length, rightIdx = nums.length - 1
nums 仅最后一个元素等于 target，例如 [1, 2, 3], target = 3，leftIdx = rightIdx = nums.length - 1，ans = [nums.length - 1, nums.length - 1] （能够成立是因为binarySearch 中 ans 初始化为 nums.length）
target > nums[0] && target < nums[nums.length - 1] 但 target 不在 nums 里，例如 [5,7,7,8,8,10], target = 6，leftIdx = 1，rightIdx = 1 - 1 = 0

举例 1 和 3 的 leftIdx > rightIdx。

解题四

当时通过了特别得意，结果对比定理一算，时间复杂度是 O ( n ) O(n) O(n)。

// javascript
var searchRange = function(nums, target) {
    return searchRangeHelper(nums, 0, nums.length - 1, target);
};

const searchRangeHelper = (nums, left, right, target) => {
    if (left === right) return nums[left] === target ? [left, left] : [-1, -1];
    const mid = left + ((right - left) >> 1);
    let leftRes = [-1, -1], rightRes = [-1, -1];
    if (target <= nums[mid]) {
        leftRes = searchRangeHelper(nums, left, mid, target);
    }
    if (target >= nums[mid + 1]) {
        rightRes = searchRangeHelper(nums, mid + 1, right, target);
    }
    if (target <= nums[mid] && target >= nums[mid + 1]) return [leftRes[0], rightRes[1]];
    return leftRes[0] === -1 ? rightRes : leftRes;
};

二分查找模板分析 & LeetCode34 在排序数组中查找元素的第一个和最后一个位置

Java相关栏目本月热门文章