二分查找

二分查找有着查找速度快,平均性能好等优点,但必须要求待查表为有序表,且插入删除困难。

二分查找思想

在算法国内的另一位大师克,听说了Bill大师给他弟子讲的冒泡排序之后,为了不落于人,决定传授弟子们一种新的算法。

次日,克唤来两名得意弟子谦子和慧子,准备考考他们

谦子和慧子来到老师跟前,只见老师在纸上写了一行数,如下:
1.png
2.png
谦子抢先答道
3.png
谦子急忙问道
4.png
慧子一边说着一边画了个图
5.png
这时慧子又画了一个图
6.png
谦子听了之后不得不佩服
7.png
慧子画出了第三张图
8.png

二分代码

9.png
慧子的代码功底还是非常强的,说着说着写了短短几行代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private static int binarySearch(int arr[], int key) {
int low = 0; // key 为待查找元素
int high = arr.length-1;
int mid;
while(low <= high) {
mid = (low + high)/2; // 查找区间的中间位置
if (arr[mid] > key) {
high = mid - 1;
} else if (arr[mid] < key) {
low = mid + 1;
} else {
return mid; // 查到返回该元素下标
}
}
return -1; // 未查到返回-1
}

10.png
慧子解释道
11.png
慧子画出了下图解释道
12.png
这时克发话了

慧子还在欣赏自认为完美无瑕的代码,听了老师的话一下变得紧张起来
13.png
慧子嘿嘿地笑了一下
14.png
15.png
克自问自答起来,顺手画了一个图
16.png
慧子恍然大悟,原来写成 mid=low+(high-low)/2 就可以了

时间复杂度

17.png
你这样想一下,你要查找的数据规模如果是n,那二分一次后规模就变为n/2^1,二分两次后规模为n/2^2,…,二分m次后规模为n/2^m,若二分m次后跳出循环,则m就是循环的次数(不管查找是否成功)
18.png

下来分析最坏情况,也就是查找不到
前提:查找不到元素

假设你二分m次后剩下一个元素,那么此时规模为1,同时二分m次后规模变为n/2^m,则:n/2^m = 1, 解出 m = lg(n),此时再循环一次,查找不到,跳出循环,所以说最多有 m+1 次循环(二分m次未跳出循环,还要二分一次),也就是查找一个元素最多需要m+1次,即lg(n)+1次比较,故二分的最坏时间复杂度为O(n) = lg(n)

lg(n) 这里是以2为底

19.png
说完克看弟子还是不是很明白,说道
20.png

x向下取整表示小于或等于x的最大整数

21.png

完。
招录自:码分享

有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%