[Python手撕]二分法
二分法
二分法的几个位置
比如
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 3 | 3 | 3 | 3 | 4 | 5 | 6 |
有时候想要寻找小于3的最大数字
有时候想要寻找第一个满足>=3的数字，
有时候想要寻找最后一个满足>=3的数字，
有时候想要寻找小于4的最大数字
nums = [1, 2, 3, 4, 5, 5, 5, 5, 5, 6, 7, 8, 9]
n = len(nums)
left = 0
right = n - 1
result = -1
target = 5
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
result = mid
left = mid + 1
else:
right = mid - 1
print(result, nums[result])
left = 0
right = n - 1
result = -1
target = 5
while left <= right:
mid = (left + right) // 2
if nums[mid] > target:
result = mid
right = mid - 1
else:
left = mid + 1
print(result, nums[result])
left = 0
right = n - 1
result = -1
target = 5
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
result = mid
right = mid - 1
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
print(result, nums[result])
left = 0
right = n - 1
result = -1
target = 5
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
result = mid
left = mid + 1
elif nums[mid] > target:
right = mid - 1
else:
left = mid + 1
print(result, nums[result])