二分查找算法，也叫折半查找算法。它针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。
**

O(logn) 惊人的查找速度

O(logn) 这种对数时间复杂度。这是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是常量级 O(1) 的算法还要高效。

为什么这么说呢？因为 logn 是一个非常“恐怖”的数量级，即便 n 非常非常大，对应的 logn 也很小。比如 n 等于 2 的 32 次方，这个数很大了吧？大约是 42 亿。也就是说，如果我们在 42 亿个数据中用二分查找一个数据，最多需要比较 32 次。所以常量级时间复杂度的算法有时候可能还没有 O(logn) 的算法执行效率高。

简单的二分查找

代码实现

二分查找的代码实现比较容易写错。你需要着重掌握它的三个容易出错的地方：循环退出条件、mid 的取值，low 和 high 的更新。

场景：有序数组中不存在重复元素

  • 非递归

二分查找的变形问题

变体一：查找第一个值等于给定值的元素

  2. public int bsearch(int[] a, int n, int value) {
  3.   int low = 0;
  4.   int high = n - 1;
  5.   while (low <= high) {
  6.     int mid =  low + ((high - low) >> 1);
  7.     if (a[mid] > value) {
  8.       high = mid - 1;
  9.     } else if (a[mid] < value) {
  10.       low = mid + 1;
  11.     } else {
  12.         //1. 判断mid == 0边界情况 
  13.         //2. 判断前一个数不等于value时则继续二分查找[low - (mid-1)]区间
  14.       if ((mid == 0) || (a[mid - 1] != value)) return mid;
  15.       else high = mid - 1;
  16.     }
  17.   }
  18.   return -1;
  19. }

变体二：查找最后一个值等于给定值的元素

  2. public int bsearch(int[] a, int n, int value) {
  3.   int low = 0;
  4.   int high = n - 1;
  5.   while (low <= high) {
  6.     int mid =  low + ((high - low) >> 1);
  7.     if (a[mid] > value) {
  8.       high = mid - 1;
  9.     } else if (a[mid] < value) {
  10.       low = mid + 1;
  11.     } else {
  12.         // 判断mid + 1是否等于value 和 边界条件
  13.       if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
  14.       else low = mid + 1;
  15.     }
  16.   }
  17.   return -1;
  18. }

变体三：查找第一个大于等于给定值的元素

  2. public int bsearch(int[] a, int n, int value) {
  3.   int low = 0;
  4.   int high = n - 1;
  5.   while (low <= high) {
  6.     int mid =  low + ((high - low) >> 1);
  7.     if (a[mid] >= value) {
  8.         // a[mid - 1] < value表明是第一个大于等于value的元素，注意边界
  9.       if ((mid == 0) || (a[mid - 1] < value)) return mid;
  10.       else high = mid - 1;
  11.     } else {
  12.       low = mid + 1;
  13.     }
  14.   }
  15.   return -1;
  16. }

变体四：查找最后一个小于等于给定值的元素

  2. public int bsearch7(int[] a, int n, int value) {
  3.   int low = 0;
  4.   int high = n - 1;
  5.   while (low <= high) {
  6.     int mid =  low + ((high - low) >> 1);
  7.     if (a[mid] > value) {
  8.       high = mid - 1;
  9.     } else {
  10.       if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
  11.       else low = mid + 1;
  12.     }
  13.   }
  14.   return -1;
  15. }

实际问题

  1. 如何快速定位出一个 IP 地址的归属地？

我们知道，IP 地址可以转化为 32 位的整型数。所以，我们可以将起始地址，按照对应的整型值的大小关系，从小到大进行排序。然后，这个问题就可以转化为我刚讲的第四种变形问题“在有序数组中，查找最后一个小于等于某个给定值的元素”了。

二分查找应用场景

  • 首先，二分查找依赖的是顺序表结构，简单说就是数组。
  • 其次，二分查找针对的是有序数据。

二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中。针对动态变化的数据集合，二分查找将不再适用。

  • 数据量太小、太大都不适合二分查找
    • 太小时，直接顺序遍历也很快。
    • 太大时，数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。
    • 只有数据量较大（看占多少内存）的时候，二分查找的优势才会比较明显。

小结

二分查找虽然性能比较优秀，但应用场景也比较有限。底层必须依赖数组，并且还要求数据是有序的。对于较小规模的数据查找，我们直接使用顺序遍历就可以了，二分查找的优势并不明显。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。