《数据结构与算法-王争》学习笔记，记录备查

二分查找

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

• 时间复杂度：O(logn)

二分查找，实现注意点

• 循环退出条件，low <= high，而不是 low < higt 。

• mid 的取值，mid = low+(high-low)/2 进一步优化，low+((high-low)>>1)

• low 和high 的更新，low=mid+1，high=mid-1 ，防止low和high相同，出现死循环。

二分查找除了用循环来实现，还可以用递归来实现。

应用场景

• 依赖顺序表结构，简单点说就是数组。

二分查找依赖下标进行操作，同时还需要随机访问才能达到时间复杂度O(logn)。

• 针对的是有序数据。

二分查找只能用在插入、删除操作不频繁、一次排序多次查找的场景。

• 数据量太小适合二分查找。

在数据量小，比较比较高效的情况下，直接遍历就足够了。在用二分查找，增加了逻辑的复杂性。但是，在数据量小，比较比较费时的时候，还是建议使用二分查找。

• 数据量太大不合适二分查找。

因为二分查找，依赖数组，而数组必须使用连续的数组空间。当数据量太大的时候，没法完全加载到内存中进行操作。