二分查找Python代码
程序员文章站
2024-03-19 14:52:58
...
遇到查找问题时,要想到二分查找
输入:一个有序数组nums[],一个要查找的目标值target
每次比较都是,中间数字与目标值比较,这样每次可以排除一半的数字,故时间复杂度是logN。
代码如下
class Solution:
def search(self, nums: List[int], target: int) -> int:
low = 0
high = len(nums)-1
while low <= high:
location = low + (high - low)//2
#为防止超过整数范围,可以写成 location = low + (high - low)//2
#便于理解可以写成mid = (low+high)//2
temp = nums[location]
if temp == target:
return location
elif temp < target:
low = location+1
else :
high = location-1
return -1
代码套路分析:
low, high = 第一个和最后一个位置
while low<=high:
找到中间位置 mid = low + (high - low)//2
if 找到target:
返回
elif :
查找范围缩小一半
else:
查找范围缩小另一半
未找到返回None
上一篇: Spring Security的使用