LeetCode 二分查找算法入门与实战

以上操作在 while(left <= right) 条件下进行，跳出循环说明未找到。

实现代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] < target) left = mid + 1;
            else if (nums[mid] > target) right = mid - 1;
            else return mid;
        }
        return -1;
    }
};

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

题目描述

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果不存在，返回 [-1, -1]。必须设计并实现时间复杂度为 O(log n) 的算法。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums 是一个非递减数组
• -10^9 <= target <= 10^9

题目分析

这是二分区间的经典例题。基础二分模板保留特定左或右下标的方式可能找不到等于 target 的值，这里需要确保找到的是等于 target 的边界。

实现思路

分别找到左边界和右边界。

找左边界： 明确区间特点：左区间 [left, k - 1] 小于 target，右区间 [k, right] 大于等于 target。

• 当 mid 在 [left, k - 1] 时，nums[mid] < target，舍弃 [left, mid]，更新 left = mid + 1。
• 当 mid 在 [k, right] 时，nums[mid] >= target，不能舍弃 k，舍弃 [left + 1, right]，更新 right = mid。 注意：此处需向下取整，避免死循环。

找右边界： 明确区间特点：左区间 [left, k] 小于等于 target，右区间 [k + 1, right] 大于 target。

• 当 mid 在 [left, k] 时，nums[mid] <= target，不能舍弃 mid，舍弃 [left, mid - 1]，更新 left = mid。
• 当 mid 在 [k + 1, right] 时，nums[mid] > target，舍弃 [mid, right]，更新 right = mid - 1。 注意：此处需向上取整。

实现代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        if (n == 0) return {-1, -1};
        
        // 找左边界
        int left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        int Left = 0;
        if (nums[left] != target) return {-1, -1};
        else Left = left;
        
        // 找右边界
        left = 0; right = n - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        return {Left, left};
    }
};

小技巧

这里给一个取整的小技巧：while 循环里有 -1，取整就要 +1；反之则没有 +1。

搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入：nums = [1,3,5,6], target = 5
输出：2

示例 2:

输入：nums = [1,3,5,6], target = 2
输出：1

示例 3:

输入：nums = [1,3,5,6], target = 7
输出：4

提示：

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• nums 为无重复元素的升序排列数组
• -10^4 <= target <= 10^4

题目分析

该题目可转换为找出大于等于目标值的最左端，复用之前写的代码。

实现思路

使用二分基础模板，标记大于等于目标值的下标。

实现代码

代码一

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int ret = -1;
        int left = 0, right = nums.size() - 1;
        if (nums[nums.size() - 1] < target) return nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
};

代码二

class Solution {
public:
    int searchInsert(vector<int>& a, int value) {
        int L = 0;
        int R = a.size() - 1;
        if (a[a.size() - 1] < value) return a.size();
        int index = -1;
        while (L <= R) {
            int mid = L + ((R - L + 1) >> 1);
            if (a[mid] >= value) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return index;
    }
};

x 的平方根

题目描述

给你一个非负整数 x，计算并返回 x 的算术平方根。由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

• 0 <= x <= 2^31 - 1

题目分析

实际求的是小于等于根号 x 的最大值，可复用第二题或第三题的代码二。

实现思路

条件改变，基本思路一致。

实现代码

代码一

class Solution {
public:
    int mySqrt(int x) {
        int left = 1, right = x;
        if (x < 1) return 0;
        while (left < right) {
            long long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return left;
    }
};

代码二

class Solution {
public:
    int mySqrt(int x) {
        int left = 1, right = x;
        if (x < 1) return 0;
        int index = -1;
        while (left <= right) {
            long long mid = left + (right - left + 1) / 2;
            if (mid * mid <= x) {
                index = mid;
                left = mid + 1;
            } else right = mid - 1;
        }
        return index;
    }
};