Leetcode 704 二分查找
题目链接:704 二分查找
关键点思路:
1、是否要进入到 while 部分的代码是 left <= right 还是 left < right, 看 [left, right] 是否是合法区间. 例如 [1, 1] 是合法区间,取<=; [1, 1) 非合法区间,取 < 。
2、缩小区间时,考虑边界是否已经比较过。
左闭右闭区间 [left, right]
class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums) - 1
while l <= r: # 左闭右闭区间
mid = (l+r) // 2
if target < nums[mid]: # mid 已经比较过,所以缩小区间取 mid - 1
r = mid - 1
elif target > nums[mid]: # mid 已经比较过,所以缩小区间取 mid + 1
l = mid + 1
else:
return mid
return -1
左闭右开区间 [left, right)
class Solution:
def search(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums) # 左闭右开,避免错过最右端的元素
while l < r: # 采用左闭右开原则 [l, r)
mid = (l+r) // 2
if target < nums[mid]:
r = mid # 缩小区间,右边为开区间
elif target > nums[mid]:
l = mid + 1 # 缩小区间,左边为闭区间,去除已比较过的 mid
else:
return mid
return -1