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;
}
最后编辑时间: 6/4/2020, 10:59:12 PM