| 题目链接 | 704. 二分查找 |
|---|---|
| 思路 | 二分法 |
| 题解链接 | 二分查找总是写不对？一个视频讲透！（Python/Java/C++/Go） |
| 关键点 | 循环不变量（开区间）：nums[left] < target && nums[right] >= target |
| 时间复杂度 | \(O(\log n)\) |
| 空间复杂度 | \(O(1)\) |
代码实现：
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = -1, len(nums)
while left + 1 < right:
mid = (left+right) // 2
if nums[mid] < target:
left = mid
else:
right = mid
if right < len(nums) and nums[right] == target:
return right
return -1