Leetcode - 二分查找 | 在排序数组中查找元素的第一个和最后一个位置

题目一：二分查找

二分查找

看到这道题之后，很快就能想到暴力的解法，把数组遍历一遍就能找到答案，时间复杂度O(n)。

假设存在一批数字[1，1，3，4，5，6，7，8]，目标数字是5。

我想在这一批数字中找到5这个数字，该如何找？当我随机挑选了一个数字4的时候，4比5小，4左边的数字都比4小，所以可以在[5,8]区间找5这个数字，继续随机挑选了7这个数字，7比5大，7后面的数字都比7大，所以可以继续缩小区间，把目标数字定位在[5,6]区间内。

二分查找算法

1. 确定查找范围的起始点和终止点。
2. 计算中间点，查看中间点的元素值与目标值的关系。
3. 如果中间点的元素值等于目标值，查找成功。
4. 如果中间点的元素值大于目标值，说明目标值可能在左半部分，缩小查找范围至左半部分。
5. 如果中间点的元素值小于目标值，说明目标值可能在右半部分，缩小查找范围至右半部分。
6. 重复以上步骤，直到找到目标值或确定目标值不在数组中。

当使用二分查找算法查找目标值时，我们首先需要一个有序数组。让我们尝试查找目标值为7的索引，假设有序数组为 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]。

初始状态： 设定查找范围的起始点（left）和终止点（right）分别为数组的第一个和最后一个元素。此时，left = 0，right = 9。

第一轮查找： 计算中间点的索引（mid）为 (left + right) >> 1 = 4，对应的值为 5。由于目标值 7 大于 5，我们缩小查找范围到右半部分。更新 left = mid + 1，即 left = 5。

第二轮查找： 新的中间点索引为 (left + right) >> 1 = 7，对应的值为 8。由于目标值 7 小于 8，我们缩小查找范围到左半部分。更新 right = mid - 1，即 right = 6。

第三轮查找： 新的中间点索引为 (left + right) >> 1 = 5，对应的值为 6。由于目标值 7 大于 6，我们缩小查找范围到右半部分。更新 left = mid + 1，即 left = 6。

第四轮查找： 新的中间点索引为 (left + right) >> 1 = 6，对应的值为 7。因此，我们找到了目标值 7，并返回索引 6。

代码解析

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

        return -1;
    }
};

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

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

暴力解法：从前往后扫描，记录下来遇到目标数字的位置即可。

代码解析

依旧使用二分，

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int t) {

        int l = 0, r = nums.size() - 1;
        int n = nums.size();
        int mid;
        int ansl = -1;
        int ansr = -1;
        if (n == 0)
        {
            return {ansl, ansr};
        }
        while (l < r)
        {   
            mid = l + (r - l >> 1);
            if (nums[mid] < t) l = mid + 1;
            else r = mid;
        }
        ansl = l;
        l = 0, r = n - 1;
        while (l < r)
        {
            mid = l + (r - l + 1 >> 1);
            if (nums[mid] > t) r = mid - 1;
            else l = mid;
        }
        ansr = l;
        if (nums[ansl] != t || nums[ansr] != t) return {-1, -1};
        return {ansl, ansr};

    }  
};

模板

// 确定左端点
while (l < r)
{   
    mid = l + (r - l >> 1);
    if (……) l = mid + 1;
    else r = mid;
}

// 确定右端点
while (l < r)
{
    mid = l + (r - l + 1 >> 1);
    if (……) r = mid - 1;
    else l = mid;
}