数据结构与算法 - 算法 - 二分查找
约 445 字大约 1 分钟
数据结构与算法查找
2023-09-08
《数据结构与算法-王争》学习笔记，记录备查
二分查找
二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 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)。
- 针对的是有序数据。
二分查找只能用在插入、删除操作不频繁、一次排序多次查找的场景。
- 数据量太小适合二分查找。
在数据量小，比较比较高效的情况下，直接遍历就足够了。在用二分查找，增加了逻辑的复杂性。但是，在数据量小，比较比较费时的时候，还是建议使用二分查找。
- 数据量太大不合适二分查找。
因为二分查找，依赖数组，而数组必须使用连续的数组空间。当数据量太大的时候，没法完全加载到内存中进行操作。