问题

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

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

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例

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

输出：[3,4]

练习

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

# your python code

思路

北海啊，要多想！

可将该问题分解为两个独立的二分查找问题：寻找目标值的左边界（第一次出现的位置）和右边界（最后一次出现的位置）。对于左边界查找，我们需要找到第一个大于等于 target 的位置。这个位置要么就是 target 第一次出现的位置，要么 target 在数组中不存在。对于右边界查找，我们需要找到最后一个小于等于 target 的位置。

• 对于左边界，采用左偏的二分 （mid = (left + right) / 2）
• 对于右边界，采用右偏的二分 （mid = (left + right + 1) / 2）

左偏二分在实际使用中很常见，其查找到的即为第一个大于等于 target 的位置。因此作为其对称的右偏二分，查找到的即为第一个小于等于 target 的位置。

Java

import java.util.Arrays;  
  
public class LC34SearchRange {  
    public static void main(String[] args) {  
        int[] nums = {5, 7, 7, 8, 8, 8, 10};  
        int target = 8;  
  
        System.out.println(Arrays.toString(searchRange(nums, target)));  
    }  
    private static int[] searchRange(int[] nums, int target) {  
        if (nums == null || nums.length == 0) return new int[]{-1, -1};  
  
        int n = nums.length;  
        int left = 0, right = n - 1, mid;  
        int lb = -1, ub = -1;  
  
        while (left < right) {  
            mid = (left + right) / 2;  
  
            if (nums[mid] < target) {  
                left = mid + 1;  
            } else {  
                right = mid;  
            }        
        }  
        if (nums[left] == target) {  
            lb = left;  
  
            left = 0;  
            right = n - 1;  
  
            while (left < right) {  
                mid = (left + right + 1) / 2;  
  
                if (nums[mid] <= target) {  
                    left = mid;  
                } else {  
                    right = mid - 1;  
                }            
            }  
            ub = left;  
        }  
        return new int[]{lb, ub};  
    }
}

复杂度分析：

• 时间复杂度：$\mathcal{O}(\log N)$。
• 空间复杂度：$\mathcal{O}(1)$。