本文最后更新于 601 天前,其中的信息可能已经有所发展或是发生改变。
二分查找
使用二分查找的条件:
- 单调递增或递减
- 存在上下界
- 能够通过索引访问(数组更适合二分查找,链表不适合)
程序模板:
left, right = 0, len(array)
while left <= right:
mid = left + (right - left) // 2
if array[mid] == target:
return True
elif array[mid] < target:
left = mid + 1
else:
right = mid -1
例题
sqrt(x)
此题为leetcode第69题实现 int sqrt(int x) 函数。计算并返回 x 的平方根,其中 x 是非负整数。由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0 or x == 1:
return x
left, right = 2, x // 2
while left <= right:
mid = left + (right - left) // 2
if mid * mid == x:
return mid
elif mid * mid < x:
left = mid + 1
else:
right = mid - 1
return right