二分查找(Binary Search)
Varsion

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

二分查找是一种非常高效的查找算法

假设数据大小是 n,每次查找后数据都会缩小为原来的一半,也就是会除以 2。最坏情况下,直到查找区间被缩小为空,才停止。

可以看出来,这是一个等比数列。其中 n/2k=1 时,k 的值就是总共缩小的次数。而每一次缩小操作只涉及两个数据的大小比较,所以,经过了 k 次区间缩小操作,时间复杂度就是 O(k)。通过 n/2k=1,我们可以求得 k=log2n,所以时间复杂度就是 O(logn)

二分查找应用场景的局限性

二分查找依赖的是顺序表结构,简单点说就是数组

二分查找算法需要按照下标随机访问元素

二分查找只能用在数据是通过顺序表来存储的数据结构上。如果数据是通过其他数据结构存储的,则无法应用二分查找。

二分查找针对的是有序数据

二分查找对这一点的要求比较苛刻,数据必须是有序的。如果数据无序,需要先排序

如果针对的是一组静态的数据,没有频繁地插入、删除,我们可以进行一次排序,多次二分查找。这样排序的成本可被均摊,二分查找的边际成本就会比较低。

如果数据集合有频繁的插入和删除操作,要想用二分查找,要么每次插入、删除操作之后保证数据仍然有序,要么在每次二分查找之前都先进行排序。针对这种动态数据集合,无论哪种方法,维护有序的成本都是很高的。

数据量太小或者太大都不适合二分查找

如果要处理的数据量很小,完全没有必要用二分查找,顺序遍历就足够了。比如在一个大小为 10 的数组中查找一个元素,不管用二分查找还是顺序遍历,查找速度都差不多。只有数据量比较大的时候,二分查找的优势才会比较明显。

二分查找的底层需要依赖数组这种数据结构,而数组为了支持随机访问的特性,要求内存空间连续,对内存的要求比较苛刻。

总结

有三种方法查找循环有序数组:

找到分界下标,分成两个有序数组
判断目标值在哪个有序数据范围内,做二分查找

找到最大值的下标 x;
所有元素下标 +x 偏移,超过数组范围值的取模;
利用偏移后的下标做二分查找;
如果找到目标下标,再作 -x 偏移,就是目标值实际下标。
 两种情况最高时耗都在查找分界点上,所以时间复杂度是 O(N)。

循环数组存在一个性质:以数组中间点为分区,会将数组分成一个有序数组和一个循环有序数组

  •  如果首元素小于 mid,说明前半部分是有序的,后半部分是循环有序数组
  •  如果首元素大于 mid,说明后半部分是有序的,前半部分是循环有序的数组
  •  如果目标元素在有序数组范围中,使用二分查找
  •  如果目标元素在循环有序数组中,设定数组边界后,使用以上方法继续查找

  • Post title:二分查找(Binary Search)
  • Post author:Varsion
  • Create time:2020-08-11 17:57:14
  • Post link:https://blog.varsion.cn/post/dda360a0.html
  • Copyright Notice:All articles in this blog are licensed under BY-NC-SA unless stating additionally.
Comments