二分查找也是一种在数组中查找数据的方法。它只能查找已经排好序的数据。
二分查找通过比较数组中间的数据与目标数据的大小，可以得知目标数据是在数组的左边还是右边。
因此，比较一次就可以把查找范围缩小一半。重复执行该操作就可以找到目标数据，或得出目标数据不存在的结论。
从如下数组中查找数字6
1 2 3 4 5 6 7 8 9
首先找到数组中间的数字5，将和6和5进行比较。
因为5 < 6 可以得知，6在5的右边，此时将不需要的数字移出查找范围
6 7 8 9
接下来寻找剩下数组中的中间位置的数字，此处为7.
因为6< 7,
所以知道6在7的左边。此时将不需要的数字移出查找范围。
6
在剩下的数组中找到中间的数字，此处为6.
因为 6 = 6 ，成功找到目标数字。
总结：
二分查找利用已排好序的数组，每次查找都可以将查找范围减半。查找范围内只剩下一个数据时查找结束。
数据量为n的数组，将其长度减半log2n次后，其中便剩下一个数据了。
时间：
也就是说，在二分查找中重复执行“将目标数据和数组中间的数据进行比较后将查找范围减半”的操作log2n次后，就能找到目标数据（如果没有找到则可以得出数据不存在的结论）。因此它的时间复杂度是O(logn)。
其他：
二分查找的时间复杂度为O(logn)，与线性查找的O(n)相比速度上得到了指数倍的提高（x = log2n,则n= 2 x）。
但是二分查找又必须建立在数据已经排好的基础上才能使用，因此添加数据必须添加到合适位置，这就需要额外耗时维护数组。
使用线性查找时候，数组中的数据可以是无需的，一次你添加数据时也无需顾虑位置，直接把它加在末尾即可，不需要耗费时间。
具体使用哪个查找方法，可以根据查找和添加操作的频率来决定。
网友评论