数据结构和算法 二分查找

数据结构和算法之美-第十一篇-二分查找

Posted by Kylen on 2019-08-21

二分查找

二分搜索算法
二分查找是我们都熟识的算法，它明确的定义是：是一种在有序数组中查找某一特定元素搜索算法

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

由此可见，二分查找的时间复杂度是O(logn)，这是一个很可怕的数字，因为数据规模 n 再怎么大，它的对数 logn 都会很小。我们都知道指数级别的增长很可怕，logn 其实就是与之对应的指数级的减小。举个例子假如 n = 210 = 1024，最多只要 10 次比较就能找到0-1024中找到我们要的数据；n = 210 = 18446744073709551616 (1844 亿亿)看清楚是亿亿，通过二分查找最多只需要比较 64 次。

小结

  • 二分查找作为对数阶的查找算法本身非常高效。
  • 但高效的前提是数据需要使用数组来存储因为数组可以通过下标实现快速访问，如果使用链表存储，时间复杂度就变成了O(n)，二分查找就没有了意义
  • 二分查找的序列必须是已经排好序的序列。

代码实现

二分查找的代码很容易实现，最简单的情况就是有序数组中不存在重复的元素。

递归实现

1
2
3
4
5
6
7
8
9
10
11
const bSearch = (arr, low, high, v) => {
  if (low > high) return -1;
  const mid = Math.floor((low + high) / 2);
  if (v < arr[mid]) {
    return bSearch(arr, low, mid - 1, v);
  } else if (v > arr[mid]) {
    return bSearch(arr, mid + 1, high, v);
  } else {
    return mid;
  }
};

循环实现

1
2
3
4
5
6
7
8
9
10
11
12
13
const bSearch = (arr, low, high, v) => {
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (v < arr[mid]) {
      high = mid - 1;
    } else if (v > arr[mid]) {
      low = mid + 1;
    } else {
      return mid;
    }
  }
  return -1;
};

总结

二分查找依赖数组，所以就有数组的弊端，数据量太大不适合使用数组存储自然无法使用二分查找，数据量太小，直接遍历和使用二分查找区别不大。
另外，数组的优势在于随机访问，插入和删除操作则比不上链表，所以对于需要频繁的插入和删除的业务场景也不适合使用数组。
最后就是使用二分查找的数据前提是先有序。

这样一看，二分查找虽然性能优秀，但是应用场景其实很有限。和之前学习的数据结构一样，我们需要结合具体的业务场景选择最合适的数据结构存储数据，算法必须建立在特定的数据结构之上。

FEATURED TAGS
数据结构和算法 二分查找
FRIENDS