二分查找(二)——找开始和结束

LeetCode_34_FindFirstAndLastPositionofElementinSortedArray

题目分析：

注意，这道题其实是结合上一题，让你明白，我们的写法是只能找最左侧值的。      
右侧值可以转换成，大于这个值的最小值，然后下标-1得到。

解法：

public static int[] searchRange(int[] nums, int target) {
    int first = findFirst(nums, 0, nums.length - 1, target);
    if (-1 != first) {
        int last = findLast(nums, 0, nums.length, target);
        return new int[]{first, last};
    }
    return new int[]{-1 ,-1};
}

public static int findFirst(int[] nums, int begin, int end, int target){
    while (begin < end){
        int mid = begin + (end - begin) / 2;
        if(nums[mid] >= target)
            end = mid;
        else
            begin = mid + 1;
    }
    return nums[begin] == target ? begin : -1;
}

public static int findLast(int[] nums, int begin, int end, int target){
    while (begin < end){
        int mid = begin + (end - begin) / 2;
        if(nums[mid] <= target)
            begin = mid + 1;
        else
            end = mid;
    }
    return nums[begin - 1] == target ? begin - 1 : -1;
}