34 Find First and Last Position of Element in Sorted Array

Leetcode

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

---

使用二分法。第二次二分还可以根据第一次的结果进行优化，不必从 0 开始，直接从第一次出现元素的地方开始也可以。时间复杂度 o(log n) ，空间复杂度 o(1)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums==null || nums.length==0) return new int[]{-1,-1};
        int first=findFirst(nums, target);
        if(first==-1) return new int[]{-1,-1};
        int last=findLast(nums,target);
        return new int[]{first, last};
    }
    
    private int findFirst(int[] nums, int target){
        int left=0; int right=nums.length-1;
        while(left<right){
            int mid=(left+right)/2;
            int cur=nums[mid];
            if(cur>=target){
                right=mid;
            } else {
                left=mid+1;
            }
        }
        if(nums[right]==target) return right;
        return -1;
    }
    
    private int findLast(int[] nums, int target){
        int left=0; int right=nums.length-1;
        while(left<right){
            int mid=(left+right+1)/2;
            int cur=nums[mid];
            if(cur<=target){
                left=mid;
            } else {
                right=mid-1;
            }
        }
        if(nums[left]==target) return left;
        return -1;
    }
}