思维理解
小时候玩的猜数字游戏:我心里想一个数字你去猜然后给你个区间(1-100)你每猜一个我都会告诉你是大了还是小了 这样你就知道那个区间去猜了 (区间就会缩小)
下面的示例说明了二分查找的工作原理。
算法讲解
二分查找要求序列本身是有序的。因此对于无序的序列,我们要先对其进行排序。现在我们手头有一有序序列:
int list[10] = {1,2,3,4,5,6,7,22,23,44};,则二分查找的过程为:
设置三个索引:low指向数组待查范围的起始元素,high指向数组待查范围的最后一个元素,middle=(low+high)/2。开始时待查范围为整个数组。
比较list[middle]与查找元素的大小关系:
- 如果list[middle]等于查找元素,则查找成功
- 如果list[middle]大于查找元素,则说明待查元素在数组的前半部分,此时缩小待查范围,令end = middle-1
- 如果list[middle]小于查找元素,则说明待查元素在数组的后半部分,此时缩小待查范围,令start = middle +1
重复执行前面两步,直到list[middle ] 等于查找元素则查找成功或low>hig查找失败。
可见,每一次元素比较都可以把待查范围缩小1/2,因此二分查找的时间复杂度为o(logn)。
注意的点
- 循环的判定条件是:
low<high
- 为了防止数值溢出:
middle = (low+high)/2
- 当
list[middle]
不等于mun
时,high = middle - 1
或low = middle + 1
代码演示(递归算法)
|
如有不足欢迎补充