leetcode704 二分查找进阶，左边界与右边界_查找数组左边界和右边届

  上一次，写了普通的二分法，但是，这种二分法对于查找数组中第一个出现目标值的位置，和最后一个出现该目标值的位置，这种题目，就无法解决了。修正后的方法如下：
左边界：

private int Solution1(int[] nums, int target) {

     if (nums == null) {
         return -1;
     }

     int left = 0;
     int right = nums.length;

     while (left < right) {
         int mid = (left + right) / 2;
         if (nums[mid] == target) {
             right = mid;
         } else if (nums[mid] < target) {
             left = mid + 1;
         } else if (nums[mid] > target) {
             right = mid;
         }
     }

     if (left == nums.length) {
         return -1;
     }
     return nums[left] == target ? left : -1;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

右边界：

private int Solution2(int[] nums, int target) {
        if (nums == null) {
            return -1;
        }
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid;
            }
        }
        if (left == nums.length) {
            return -1;
        }
        return nums[left - 1] == target ? left - 1 : -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

  需要注意的是，不论是左边界还是右边界，更新left值的时候，都必须给 mid+1，因为
当left+1=right的时候， int mid = (left + right) / 2;这个条件计算的mid值是等于left的，如果不加1，就会陷入无限的死循环当中。
  其次，需要注意的是，因为left更新的时候，需要加1，所以，最后返回下标的时候，就需要减1。