34. Search for a Range

https://leetcode.com/problems/search-for-a-range/description/

题解很容易，只要判断:

• 比 target 小的最大值index，high = mid - 1 if nums[mid] >= target
• 比 target 大的最小值index。low = mid + 1 if nums[mid] <= target

结果：

• 如果两者相差为1，说明array中不存在该 target，按照题目要求返回 [-1, -1].
• 如果两者相差不为1，说明 array 中存在该 target，return [leftIndex + 1, right -1]

代码：

public int[] searchRange(int[] nums, int target) {
    int[] rangeIndex = new int[] {-1, -1};
    if (nums == null || nums.length == 0) {
        return rangeIndex;
    }
    
    int start = 0;
    int end = nums.length - 1;
    int mid, leftIndex, rightIndex;
    
    // find the index of biggest item that is less than target
    while (start <= end) {
        mid = start + (end - start) / 2;
        if (nums[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    
    leftIndex = end;
    start = 0;
    end = nums.length - 1;
    
    // find the index of smallest item that is greater than target
    while (start <= end) {
        mid = start + (end - start) / 2;
        if (nums[mid] <= target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }

    rightIndex = start;
    if (rightIndex != leftIndex + 1) {
        rangeIndex[0] = leftIndex + 1;
        rangeIndex[1] = rightIndex - 1;
    }
    
    return rangeIndex;
}