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].

这道题目同样采用二分法，当找到目标元素后，因为存在重复元素，我们要从当前元素向两边扩散，然后得到一个范围。如何记录呢，我们可以new一个包含两个元素的数组result，当找到目标元素时,记录当前元素的下标m，让result[0] = m, result[1] = m, 然后以m为中心，向两边比较，左边相等的就让result[0]减1，右边相等的就让result[1]加1。最终得到了包含目标元素的范围。代码如下：

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