经典查找算法

二分法查找

20210313090428873

二分搜索用于在一个单调或者局部单调有序数组中查找一个符合某些条件的值，时间复杂度为O(logN)。

1. 假设数量为N

2. 第一次查找位置为 N / 2，第二次查找为N / 4，后面依次为 N / 8...

3. 那么查找次数与N之间的关系为 2 ^ x = N

4. 所以，查找次数的时间复杂度的大O记法可表示为 O(logN)（以2为底）

代码示例：

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

   /**
    * 在一个有序数组中，找出某个数是否存在
    */
   public boolean binarySearchExist(int[] sortedArray, int num) {
     if (sortedArray == null || sortedArray.length == 0) {
       return false;
     }
     int L = 0;
     int R = sortedArray.length - 1;
     int mid = 0;
     while (L < R) {
       // mid = (L + R) / 2;
       // 防止 L + R 所得的结果过大，溢出int类型最大值
       // 改造
       // mid = L + (R - L) / 2; // R 不会溢出，L 不会溢出， (R - L) / 2 更不会造成溢出
       // 等同于
       mid = L + ((R - L) >> 1);
       if (sortedArray[mid] == num) {
         return true;
       } else if (sortedArray[mid] > num) {
         R = mid;
       } else {
         L = mid;
       }
     }
     return sortedArray[mid] == num;
   }

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

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

4. 局部最小值问题