二分搜索

Search for a Range

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

分析

可以分两次来寻找，左边界和右边界。 用两个指针不断去逼近右边界。

code

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

        int[] result = new int[2];
        int start = 0;
        int end = nums.length - 1;
        // 确保如果arrayx的长度和Integer.MAX_VALUE不会出现问题。
        int mid = start + (end - start) / 2;

        // search for right bound
        while(start + 1 < end) {
            // 因为是在找右边界，所以找到中间值的时候，设为新起点
            if(nums[mid] == target) {
                start = mid;
            } else if(nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        // 最后停下来的两个位置都有可能是右边界的值
        if(nums[end] == target) {
            result[1] = end;
        } else if(nums[start] == target) {
            result[1] = start;
        } else {
            result[0] = result[1] = -1;
            return result;
        }

        // search for left bound
        start = 0;
        end = nums.length - 1;
        mid = start + (end - start) / 2;
        while(start + 1 < end) {
            if(nums[mid] == target) {
                end = mid;
            } else if(nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if(nums[start] == target) {
            result[0] = start;
        } else if(nums[end] == target){
            result[0] = end;
        } else {
            result[0] = result[1] = -1;
            return result;
        }

        return result;
    }
}