力扣(LeetCode)- 二分查找算法(Binary Search) 收藏 阅读:55
2020-11-18 16:57:01

1. 什么是二分查找算法

二分查找(Binary Search),又称折半查找算法。是对有序数据,通过每次折半,通过判断中间位置数据大小不断缩小查找范围来查找的算法。

二分查找算法时间复杂度是O(longn),效率很高。

2. 二分查找算法实现

首先,非递归实现,通过while循环。

   /**
    * 普通实现
    * @param arr
    * @param value
    * @return
    */
   public static int binSearchNoRecursion(int[] arr, int value) {
       int low = 0;
       int high = arr.length - 1;

       if (high == 0) {
           return -1;
      }

       while (low <= high) {
           int mid = low + ((high - low) >> 1);

           if (arr[mid] == value) {
               return mid;
          } else if (arr[mid] < value) {
               low = mid + 1;
          } else {
               high = mid - 1;

          }
      }

       return -1;
  }

再次,递归实现。递归实现请注意,一定要包含递归公式和递归结束条件。

   /**
    * 递归实现
    * @param arr
    * @param low
    * @param high
    * @param value
    * @return
    */
   public static int binSearch4oRecursion(int[] arr, int low, int high, int value) {
       if (arr.length == 0 || low > high) {
           return -1;
      }

       int mid = low + ((high - low) >> 1);
       if (arr[mid] == value) {
           return mid;
      } else if (arr[mid] < value) {
           return binSearch4oRecursion(arr, mid + 1, high, value);
      } else {
           return binSearch4oRecursion(arr, low, mid - 1, value);
      }
  }

注意,这里mid的取值为什么是low + ((high - low) >> 1),而不是(low+high)/2 ?

  • 当low和high数据量很大的时候,两值相加有可能数据溢出。

  • 通过位移运算效率高

3. 二分查找适用情况

第一点,只适合有序数据。

这个很好理解,无序数据通过二分查找没有意义。

第二点,二分查找适合数组这种数据结构

当要查找的数据是链表的时候,就尴尬了。众所周知,链表不支持随机访问,比较数据时候,需要一个一个的遍历,效率很低。

而数组就不同了,支持随机访问。

第三点,二分查找不适合数据量很大的情况

通过二分查找的数据是数组,而数组的特点就是创建时就分配好了空间,当数据量非常大的时候,一次需要的存储空间非常大,所以该情况使用请慎重。


读后有收获,请作者喝杯咖啡


全部评论

发表评论