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

二分查找

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

  • 针对的是有序数据。

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

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

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

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

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