一、算法简介
折半查找又叫二分查找,要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列(升序或者降序)。
- 时间复杂度:O(log2n)
每次循环都会舍弃一半的查找空间。
- 空间复杂度:O(1)
使用一个整型变量mid记录中间的值。
二、算法思路
需要用到三个指针:low,high,mid
初始时,low指向列表的第一个元素,high指向列表的最后一个元素。
mid指向列表中间的元素。需要查找的目标值为target,当target的值小于mid指向的值,说明目标值在前半部分,此时需要把指针high移动到指针mid的左边。反之,需要把指针low移动到指针mid的右边。
mid = (low +high)//2
注意这里使用的是地板除
查找结束条件:low > high
三、具体编码
def binSearch(nums,target):
low = 0
high = len(nums)-1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
elif nums[mid] > target:
high = mid - 1
elif nums[mid] < target:
low = mid + 1
a = binSearch([1,3,5,7,8,9],3)
print(a)