TIP

二分查找

• 2020-06-04 练习一次

代码模板

public int binarySearch(int[] arr, int v) {
    int l = 0;
    int r = arr.length - 1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (arr[mid] == v)
            return mid;
        else if (arr[mid] < v)
            l = mid + 1;
        else if (arr[mid] > v)
            r = mid - 1;
    }
    return -1;
}

WARNING

二分查找中容易出错的点

循环退出的地方

注意是 l <= h 不是 l < h

mid 的取值

实际上，mid=(low+high)/2 这种写法是有问题的。因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。改进的方法是将 mid 的计算方式写成 low+(high-low)/2。更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 low+((high-low)>>1)。因为相比除法运算来说，计算机处理位运算要快得多

l 和 h 的更新

l = mid + 1，h = mid - 1。注意这里的 +1 和 -1，如果直接写成 l = mid 或者 h = mid，就可能会发生死循环。比如，当 h = 3，l = 3 时，如果 a[3] 不等于 value，就会导致一直循环不退出。

findTheFirstValue

   /**
     * 找到在数组中第一出现的位置
     * @param arr
     * @param target
     * @return
     */
    public int findTheFirstValue(int[] arr, int target) {
        int n = arr.length;
        int l = 0;
        int r = n - 1;

        while(l <= r) {
            int mid = l + ((r - l) >>> 2);

            if (arr[mid] > target) {
                r = mid - 1;
            } else if (arr[mid] < target) {
                l = mid + 1;
            } else {
                if (mid == 0 || arr[mid - 1] != target) {
                    return mid;
                }
                r = mid - 1;
            }
        }

        return -1;
    }

findTheLastValue

/**
     * 找到这最后一个值
     * @param arr
     * @param target
     * @return
     */
public int findTheLastValue(int[] arr, int target) {
  int n = arr.length;
  int l = 0;
  int r = n - 1;

  while(l <= r) {
    int mid = l + ((r - l) >>> 2);

    if (arr[mid] > target) {
      r = mid - 1;
    } else if (arr[mid] < target) {
      l = mid + 1;
    } else {
      if (mid == n - 1 || arr[mid + 1] != target) {
        return mid;
      }
      l = mid + 1;
    }
  }

  return -1;
}