Search for a Range

Given an array of integersnumssorted in ascending order, find the starting and ending position of a giventargetvalue.

Your algorithm's runtime complexity must be in the order ofO(logn).

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

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]

Analysis

寻找有重复的有序数列中的特定元素的下标范围，需要寻找左边界和右边界。这样单一的binary search会比较难实现，因此用两个binary search，一个找左边界，一个找右边界。

比较偏好Template #3，left + 1 < right作为循环条件，这样结尾的时候有两个备选，满足left + 1 >= right。

寻找左边界

if (target <= nums[mid]) {
    right = mid;
} else {
    left = mid;
}

寻找右边界

if (target >= nums[mid]) {
    left = mid;
} else {
    right = mid;
}

区别就在于target == nums[mid]时，是往右搜索（右边界）还是往左搜索（左边界）。

Solution

Using Template #3 - Two Binary Searches (6 ms, 33.53%)

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[] {-1, -1};
        if (nums == null || nums.length == 0) return res;

        int left, right;

        // Binary Search 1 - Left Boundary        
        left = 0; 
        right = nums.length - 1;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            if (target <= nums[mid]) {
                right = mid;
            } else {
                left = mid;
            }
        }

        if (nums[left] == target) {
            res[0] = left;
        } else if (nums[right] == target) {
            res[0] = right;
        }

        // Binary Search 2 - Right Boundary
        left = 0; 
        right = nums.length - 1;

        while (left + 1 < right) {
            int mid = left + (right - left) / 2;

            if (target >= nums[mid]) {
                left = mid;
            } else {
                right = mid;
            }
        }

        if (nums[right] == target) {
            res[1] = right;
        } else if (nums[left] == target) {
            res[1] = left;
        }

        return res;
    }
}

Combined two binary searches In Helper function - (6ms 33.53%)

class Solution {
    // returns leftmost (or rightmost) index in `nums` for `target` via binary search.
    private int extremeInsertionIndex(int[] nums, int target, boolean leftMost) {
        if (nums == null || nums.length == 0) return -1;
        int lo = 0;
        int hi = nums.length - 1;

        while (lo + 1< hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] > target || (leftMost && target == nums[mid])) {
                hi = mid;
            }
            else {
                lo = mid;
            }
        }
        if (leftMost) {
            if (nums[lo] == target) {
                return lo;
            } else if (nums[hi] == target){
                return hi;
            }
        } else {
            if (nums[hi] == target) {
                return hi;
            } else if (nums[lo] == target){
                return lo;
            }
        }
        return -1;
    }

    public int[] searchRange(int[] nums, int target) {
        int[] targetRange = {-1, -1};

        int leftIdx = extremeInsertionIndex(nums, target, true);
        int rightIdx =  extremeInsertionIndex(nums, target, false);

        targetRange[0] = leftIdx;
        targetRange[1] = rightIdx;

        return targetRange;
    }
}