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

题目

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

解题

方法一：二分查找 中心扩散

思路

二分查找裸题，首先二分查找找到目标元素索引，然后从索引开始分别向左右两边扩散直到遇到与目标元素不同的元素停止，于是就找到了目标元素的左右边界并返回。

二分查找 - 相等

代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return new int[]{-1, -1};
        }
        if (len == 1 && target == nums[0]) {
            return new int[]{0, 0};
        }
        int targetIdx = -1;
        int start = 0, end = len - 1;

        while(start <= end) {
            int mid = start + ((end - start) >> 1);

            if (target == nums[mid]) {
                targetIdx = mid;
                break;
            } else if (target < nums[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        if (targetIdx == -1) {
            return new int[]{-1, -1};
        } else {
            int lastTargetIdx = targetIdx;
            while (targetIdx > 0 && target == nums[targetIdx - 1]) {
                targetIdx--;
            }
            while (lastTargetIdx < len - 1 &&
                    target == nums[lastTargetIdx + 1]) {
                lastTargetIdx++;
            }
            return new int[]{targetIdx, lastTargetIdx};
        }
    }
}

方法二：二分查找左右边界

思路

直接两次二分查找分别查找目标元素的左右边界。

二分查找 - 相等 - 左边界 二分查找 - 相等 - 右边界

代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[2];
        int len = nums.length;
        int start = 0, end = len - 1;
        while (start <= end) {
			int mid = start + ((end - start) >> 1);
			if (nums[mid] < target) start = mid + 1;
			else end = mid - 1;
		}
		ans[0] = (start != len && nums[start] == target) ? start : -1;
        start = 0;
        end = len - 1;
        while (start <= end) {
			int mid = start + ((end - start) >> 1);
			if (nums[mid] <= target) start = mid + 1;
			else end = mid - 1;
		}
        ans[1] = (end != -1 && nums[end] == target) ? end : -1;
        return ans;
    }
}