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

对于二分查找，我们经常头疼于它的边界值问题，是要【左闭右开】（即[left, right) ）进行搜索？还是【左闭右闭】（即[left,right] ）进行搜索？对于【左闭右开】的写法，在左右收敛时我们时常要考虑向左半段搜索时mid是否要-1后再赋给right，或向右半段搜索时mid是否要+1后再赋值给left的问题，想着想着开始怀疑人生。。。

相对于【左闭右开】，【左闭右闭】的写法就比较统一，不过往左还是右，mid都需要做一次+1或-1的操作，比较方便记忆，当然如果你写熟了并且理解了两种写法，right的开闭完全取决你的心情。。这里提供一个标准的【左闭右闭】的二分查找模板，认准了这个模板，后面我们均按这个模板来作答。

    /**
     * 标准二分的模板
     *
     * @param nums
     * @param target
     * @return
     */
    private int search_template(int[] nums, int target) {
        // 左闭右闭
        int left = 0, right = nums.length - 1;
        // 终止条件为left=right+1
        while (left <= right) {
            // 如果写成(left+right)>>1，可能溢出
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return -1;
    }

如果模板上面的模板看明白了，那么这道题就不难解答，我们分别定义一个寻找左边界的方法leftBound和一个寻找右边界的方法rightBound：

相对于二分查找模板，这里多了三步（比如说寻找左边界的方法）：

1、在发现找到一个target对象时，不返回，而是继续让right=mid-1，也就是向左边收敛，找左边界；

2、后面有两个返回-1的条件，我们一起来看一下：

• left ≥ nums.length ：这一步考虑的是如果出现当前数组中所有的元素都小于target元素，那么在跳出循环前会最后一次进入nums[mid] < target的分支，而最后一次left=mid+1后，left会越界，因此我们要考虑left越界的情况；
• nums[left] ≠ target：这一步考虑的是，如果数组中不存在target的情况，那么此时left指向的元素便不是我们要的左边界；

3、最后返回left，即为要寻找的左边界。

右边界同理，不再赘述。

public class Solution {

    public int[] searchRange(int[] nums, int target) {
        return new int[]{leftBound(nums, target), rightBound(nums, target)};
    }

    private int leftBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 继续向左边收敛
                right = mid - 1;
            }
        }
        // 检查是否越界，或者不存在
        if (left >= nums.length || nums[left] != target) {
            return -1;
        }
        return left;
    }

    private int rightBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                // 继续向右边收敛
                left = mid + 1;
            }
        }
        // 检查是否越界，或者不存在
        if (right < 0 || nums[right] != target) {
            return -1;
        }
        return right;
    }

}