二分法

二分查找

二分查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。

二分法查找的思路如下：

1. 首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。
2. 如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤1的操作。
3. 如果某一步，数组没有输进行查找，则表示找不到目标元素。

时间复杂度：$O(log_{2}n)$

例如以下问题，都可以用二分法解决：

1. 在一个有序数组中，找某个数是否存在。

public static boolean bsExist(int[] sortedArr, int num) {
  if (sortedArr == null || sortedArr.length == 0) {
    return false;
  }
  int L = 0;
  int R = sortedArr.length - 1;
  int mid = 0;
  // L..R 至少两个数的时候
  while (L < R) { 
    // 这种写法更安全
    mid = L + ((R - L) >> 1);
    if (sortedArr[mid] == num) {
      return true;
    } else if (sortedArr[mid] > num) {
      R = mid - 1;
    } else {
      L = mid + 1;
    }
  }
  return sortedArr[L] == num;
}

PS：常见技巧写法，n >> 1 等于 n/2 ，n << 1 等于 n * 2 ，（ n << 1 ）+ 1 等于 （ n << 1 ）｜ 1

2. 在一个有序数组中，找>=某个数最左侧的位置

public static int bsNearLeft(int[] arr, int value) {
  int L = 0;
  int R = arr.length - 1;
  // 记录最左的位置
  int index = -1;
  // L..R 至少一个数的时候
  while (L <= R) {
    int mid = L + ((R - L) >> 1);
    if (arr[mid] >= value) {
      index = mid;
      R = mid - 1;
    } else {
      L = mid + 1;
    }
  }
  return index;
}

3. 在一个有序数组中，找>=某个数最右侧的位置

public static int bsNearRight(int[] arr, int value) {
  int L = 0;
  int R = arr.length - 1;
  // 记录最右的位置
  int index = -1;
  while (L <= R) {
    int mid = L + ((R - L) >> 1);
    if (arr[mid] <= value) {
      index = mid;
      L = mid + 1;
    } else {
      R = mid - 1;
    }
  }
  return index;
}

非必要条件-有序

有序并不是所有问题求解时使用二分的必要条件，只要能够正确构建左右两侧的淘汰逻辑，就可以二分，例如局部最小值问题。

问题：给定一个无序的数组，任意相邻元素不相等，返回一个局部最小元素即可。局部最小值的定义：

1. $a_{0}$ < $a_{1}$，则$a_{0}$ 局部最小。
2. $a_{n-1}$ > $a_{n}$，则$a_{n}$ 局部最小。
3. $a_{i-1}$ < $a_{i}$ < $a_{i + 1}$，则$a_{i}$ 局部最小。

public static int bsAwesome(int[] arr) {
  if (arr == null || arr.length == 0) {
    return -1; 
  }
  if (arr.length == 1 || arr[0] < arr[1]) {
    return 0;
  }
  if (arr[arr.length - 1] < arr[arr.length - 2]) {
    return arr.length - 1;
  }
  int left = 1;
  int right = arr.length - 2;
  int mid = 0;
  while (left < right) {
    mid = left + ((right - left) >> 1);
    if (arr[mid] > arr[mid - 1]) {
      right = mid - 1;
    } else if (arr[mid] > arr[mid + 1]) {
      left = mid + 1;
    } else {
      return mid;
    }
  }
  return left;
}