欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找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
	
	
相关标签: 算法