7.25 第一次做，无法 AC
7.26 无法 AC
7.28 无法 AC
7.29 无法 AC
7.30 一次 AC

题目描述

原题链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/

解题思路：二分法

这题看《 labuladong 的算法小抄》 P73 左闭右闭的二分查找。

7.29 踩坑感悟：

• 下面第11行与30行中，若 nums[m] 与 target 相等，这里就只说第11行的情况：因为要找左边界，则 r 需要向左收缩，那是 r = m 呢还是 r = m - 1 呢？答案是后者。

• 采用了 r = m - 1 后，不用去担心这种情况：r 第一次直接命中了最左边的 target 导致 r 在 target 左边，而需要的正确答案 l 却还在索引 0 处，l 会不会没办法正确指到最左边的 target ？答案是不会！

• l 会一直往右，直到越过 r 到达最左边的 target 然后满足循环退出的正常退出，此时的 l 正确指向了最左边的 target！

• 为什么会这样呢？因为前提是 r 已经指向了最左边的 target 的前一个元素，而数组是有序的，那 l 和 r 之间的数一定都小于 target ，所以 l 会一直往右移动，直至越过 r 到达最左边的 target ！

  class Solution {
    public int search(int[] nums, int target) {
        int left, right;
        // 找左侧边界
        int l = 0, r = nums.length - 1; // 搜索区间为 [left, right] 两端都闭区间
        while(l <= r) {
            int m = l + r >> 1; // l + (r - l) >> 1 可以防止 int 越界
            if(target > nums[m]) l = m + 1;
            else if(target < nums[m]) r = m - 1;
            else if(target == nums[m]) r = m - 1; // 收缩右边界
        }
        // 防止 l 越界, r 越界没关系,或者说 r 就是要越界的，可以越界的！
        // 比如数组只有一个数 [1], target 也是 1 
        // 此时 target 就等于 nums[m], 所以 r 要减一变成 -1 
        // 此时就退出循环了,而索引 l 的值仍然是 1 , 1 并不小于 -1 是会直接跳出循环的！
        // 而如果下面 || 之后的判断条件变成判断 r 越界的话，那正确结果无论如何也得不到
        // 所以 || 后面的判断条件只需判断 nums[l] 是否等于 target 即可，用来应对只有1个数的情况  
        if(l > nums.length - 1 || nums[l] != target) return 0;
        left = l;
        // 找右侧边界
        l = 0; r = nums.length - 1; // 搜索区间为 [left, right] 两端都闭区间
        while(l <= r) {
            int m = l + r >> 1;
            if(target > nums[m]) l = m + 1;
            else if(target < nums[m]) r = m - 1;
            else if(target == nums[m]) l = m + 1; // 收缩左边界
        }
        // 防止 r 越界以及一个数的情况下 l > r 提前退出循环而 nums[r] != target情况
        if(r < 0 || nums[r] != target) return 0;
        right = r;
        return right - left + 1;
    }
  }