34. Search for a Range

Given a sorted array of integers, 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].

For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

requires 2 binary search,

public class Solution {
    public int[] searchRange(int[] nums, int target) {

        int[] res = new int[]{-1,-1};
        if(nums == null || nums.length == 0) return res;
        if(nums[0] > target || nums[nums.length-1] < target) return res;

        int l =0;
        int r = nums.length-1;// eventually l may reach nums.length-1 by `l = mid +1`

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

        if(nums[l] != target) return res;
        res[0] = l;

        r = nums.length;// l may reach nums.length since the last number is the closing number,
        //so both r and l == nums.length, and r -1 is the border.
        while(l < r){
            int mid = l + (r-l)/2;
            if(nums[mid]  > target){
                r = mid;
            }else{
                l = mid +1;
            }
        }

        res[1] = r-1;

        return res;
    }
}