题目
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

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

答案

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = 0, r = nums.length, candidate = -1;
        while(l < r) {
            int mid = (l + r) / 2;
            if(nums[mid] < target) {
                l = mid + 1;
            }
            else if(nums[mid] > target) {
                r = mid;
            }
            else {
                // found
                candidate = mid;
                break;
            }
        }
        if(candidate == -1) return new int[]{-1,-1};
        r = l = candidate;
        while(l >= 0 && nums[l] == target) l--;
        while(r < nums.length && nums[r] == target) r++;
        return new int[] {l+1, r-1};
    }
}