Leet704.二分查找

给定一个n个元素有序的升序整型数组nums和一个目标值target写一个函数搜索nums中的target如果target存在返回下标否则返回-1。你必须编写一个具有O(log n)时间复杂度的算法。示例示例 1输入nums [-1,0,3,5,9,12],target 9输出4符合预期。示例 2输入nums [-1,0,3,5,9,12],target 2输出-1符合预期。代码左闭右闭区间class Solution(object): def search(self, nums, target): :type nums: List[int] :type target: int :rtype: int left, right 0, len(nums) - 1 # 定义target在左闭右闭的区间里[left, right] while left right: middle left (right - left) // 2 if nums[middle] target: right middle - 1 # target在左区间所以[left, middle - 1] elif nums[middle] target: left middle 1 # target在右区间所以[middle 1, right] else: return middle # 数组中找到目标值直接返回下标 return -1 # 未找到目标值版本二左闭右开区间class Solution: def search(self, nums: List[int], target: int) - int: left, right 0, len(nums) # 定义target在左闭右开的区间里即[left, right) while left right: # 因为left right的时候在[left, right)是无效的空间所以使用 middle left (right - left) // 2 if nums[middle] target: right middle # target 在左区间在[left, middle)中 elif nums[middle] target: left middle 1 # target 在右区间在[middle 1, right)中 else: return middle # 数组中找到目标值直接返回下标 return -1 # 未找到目标值