【数据结构】谈一下二分查找？
二分查找对计算机出身的人都不陌生，最近刷题发现二分查找的效率真的蛮高，而且用法也很多样，今天就来浅谈一下二分查找吧。
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
局限性
二分查找依赖于顺序表结构。
二分查找按照下标访问元素，不适合链表等其他数据结构。
2. 针对有序数据。
这一点要求比较严格，数据必须有序。
3. 数据量太大太小都不合适。
数据量太小的话，直接遍历就可；数据量太大的话，需要额外的空间，就会对空间的要求更高。
笔记回顾：