34. 在排序数组中查找元素的第一个和最后一个位置

二分

在这题再加深二分法的理解：
首先，闭区间的二分法标志是：判定条件为l <= r。在本题因为要求lowerbound，在循环时，维持循环不变量：nums[l - 1] < target和nums[r + 1] >= target。最后的下标为left。如果是求upperbound则最后的下标为right，并且循环不变量也跟着改变。

需要注意的点有几个。首先，在最后如果没有找到大于等于target的值，l会超过数组的右边界。而且，我们可以注意到循环不变量在一开始时似乎会越界，对此我们只需要想象成数组的左边界-1的值是负无穷大，右边界+1是正无穷大即可。

代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int []ans = new int[2];
        ans[0] = -1;
        ans[1] = -1;
        int start = bs(nums, target);
        if (start < nums.length && nums[start] == target) ans[0] = start;
        else return ans;
        int end = bs(nums, target + 1) - 1;
        ans[1] = end;
        return ans;
    }

    int bs(int []nums, int target) {
        int l = 0;
        int r = nums.length - 1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] >= target) r = mid - 1;
            else l = mid + 1;
        }
        return l;
    }
}