vlambda博客
学习文章列表

【数据结构】谈一下二分查找?



二分查找对计算机出身的人都不陌生,最近刷题发现二分查找的效率真的蛮高,而且用法也很多样,今天就来浅谈一下二分查找吧。


01

二分思想


具体的二分查找的方法就不赘述了,总结一下就是:二分查找针对的是一个有序的数据集合,每次都通过和区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为0.


二分查找的代码:

public int bsearch(int[] a, int n, int value) { int low = 0; int high = n - 1;
 while (low <= high) {  int mid = (low + high) / 2;  if (a[mid] == value) {  return mid;   } else if (a[mid] < value) {  low = mid + 1;  } else {  high = mid - 1;   } }
 return -1; }

这里有三个需要注意的地方:

  • 循环的退出条件:是low<=high, 而不是low < high。

  • mid的取值:这里需要考虑数据太大的话,会存在溢出的情况。所以写成mid = low + (high + low)/2更好。

  • low和high的更新:low = mid + 1;high = mid - 1;如果没有加一减一的话,会陷入死循环。



02

局限性


  1. 二分查找依赖于顺序表结构。

    二分查找按照下标访问元素,不适合链表等其他数据结构。

2. 针对有序数据。

    这一点要求比较严格,数据必须有序。

3. 数据量太大太小都不合适。

    数据量太小的话,直接遍历就可;数据量太大的话,需要额外的空间,就会对空间的要求更高。



笔记回顾: