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

题目

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 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

解答

STL 方法

C++ 代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();

        int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        int r = upper_bound(nums.begin(), nums.end(), target) - nums.begin();

        if (l >= n || nums[l] != target) {
            return {-1, -1};
        }

        return {l, r - 1};
    }
};

Python 代码

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)

        l = bisect.bisect_left(nums, target)
        r = bisect.bisect_right(nums, target)

        if l >= r or nums[l] != target:
            return [-1, -1]
        
        return [l, r - 1]

LeetCode 里面好像可以直接写 bisect_left 而不用写 bisect.bisect_left。

手写两遍二分查找

C++ 代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();

        int l = 0;
        int r = n;

        while (l < r) {
            int mid = l + r >> 1;

            if (nums[mid] < target) {
                l = mid + 1;
            }
            else {
                r = mid;
            }
        }

        if (l >= n || nums[l] != target) {
            return {-1, -1};
        }

        int start = l;

        l = 0;
        r = n;

        while (l < r) {
            int mid = l + r >> 1;
            
            if (nums[mid] <= target) {
                l = mid + 1;
            }
            else {
                r = mid;
            }
        }

        return {start, l - 1};
    }
};

Python 代码

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)

        l = 0
        r = n

        while l < r:
            mid = (l + r) // 2

            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid
        
        if l >= n or nums[l] != target:
            return [-1, -1]
        
        start = l

        l = 0
        r = n

        while l < r:
            mid = (l + r) // 2

            if nums[mid] <= target:
                l = mid + 1
            else:
                r = mid
        
        return [start, l - 1]

用一个函数实现

C++ 代码

class Solution {
public:
    int binarySearch(vector<int>& nums, int target, bool lower) {
        int l = 0;
        int r = nums.size();

        while (l < r) {
            int mid = (l + r) / 2;

            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }

        return l - !lower;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int left = binarySearch(nums, target, true);
        int right = binarySearch(nums, target, false);

        if (left < nums.size() && nums[left] == target) {
            return {left, right};
        }

        return {-1, -1};
    }
};

注意：

• nums.size() 是一个无符号的整数，也就是说 0 - 1 将会得到一个大正整数
• 应该写成 (int)nums.size() - 1

找到左端点后遍历

C++ 代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();

        int l = 0;
        int r = n;
        int start = -1;
        int end = -1;

        while (l < r) {
            int mid = (l + r) / 2;

            if (nums[mid] < target) {
                l = mid + 1;
            }
            else if (nums[mid] > target) {
                r = mid;
            }
            else {
                start = mid;
                end = mid;

                while (start > 0 && nums[start - 1] == target) {
                    start --;
                }

                while (end < n - 1 && nums[end + 1] == target) {
                    end ++;
                }

                break;
            }
        }

        return {start, end};
    }
};