Leetcode 34. 在排序数组中查找元素的第一个和最后一个位置
二分查找的细节
1、while 的条件，是 left <= right 还是 left < right ？
-
如果
left, right = 0, len(nums) - 1，那么搜索区间是双闭区间，[left, right]，当搜索区间为空时，搜索终止。 此时应该是[left, left - 1]所以while的条件是left <= right -
如果
left, right = 0, len(nums), 那么搜索区间是左闭右开，[left, right)，当搜索空间为空时，搜索终止。 此时应该是[left, left)所以while的条件是left < right
2、left/right = mid 还是 mid + 1、mid - 1 ?
此时看我们的目的：
经典二分查找
left, right = 0, len(nums)-1 # 双闭区间
while left <= right:
mid = (left + right)//2
if nums[mid] == target:
return mid
elif nums[mid] > target:
right = mid - 1 # 因为此处是双闭区间，mid 不满足条件，那么新的区间需要排除 mid
elif nums[mid] < target: # 为了直观，都写成 elif 的形式
left = mid + 1 # 理由同上
找左边界
left, right = 0, len(nums) # 左闭右开
while left < right: # 左闭右开，所以是 left < right
mid = (left + right)//2
if nums[mid] == target:
right = mid
# 找左边界，实质上是找比 target 小的数的个数
# nums[mid] == target时，下次循环是mid左侧
# 且由于是左闭右开区间，right = mid 就会把 mid 排除在外
elif nums[mid] > target:
right = mid
elif nums[mid] < target: # 为了直观，都写成 elif 的形式
left = mid + 1 # 左侧闭区间，需要排除 mid
return left
这样得出的 left 即是数组中小于 target 的个数。
如果对于最后的left有nums[left] != target, 那么 target 就不存在于数组中（如果target在数组中，那么刚好大于等于target的值必然是target本身）
找右边界
对找左边界代码稍作修改，即可得到找右边界的代码。其中可以逼近右边界的核心是：
if nums[mid] == target:
left = mid + 1
即如果 nums[mid] == target，继续搜索数组右侧的部分，当然这样得到的右边界是数组右侧最接近 target 的（这个思想也可以用在寻找最长子序列的改进算法中）。
代码：
left, right = 0, len(nums) # 左闭右开
while left < right: # 左闭右开，所以是 left < right
mid = (left + right)//2
if nums[mid] == target:
left = mid + 1
# 左闭右开，left = mid + 1 就会把 mid 排除在外
elif nums[mid] > target:
right = mid
elif nums[mid] < target: # 为了直观，都写成 elif 的形式
left = mid + 1 # 左侧闭区间，需要排除 mid
return left - 1 # 重要
我们可以理解为，left 即是数组中所有小于等于 target 的个数
题解
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
if n == 0:
return [-1, -1]
if nums[0] > target or nums[-1] < target:
return [-1, -1]
def find_bound(nums, target, _left = True): # left 表示求左边界还是右边界
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if _left and nums[mid] == target: # 求左边界
right = mid
elif not _left and nums[mid] == target:
left = mid + 1
elif nums[mid] > target:
right = mid
elif nums[mid] < target:
left = mid + 1
return left
# 合并之后的写法
# while left < right:
# mid = (left + right) // 2
# if nums[mid] < target or \
# (_left and nums[mid] == target):
# right = mid
# else:
# left = mid + 1
l_bound = find_bound(nums, target)
if nums[l_bound] != target:
return [-1, -1]
return [l_bound, find_bound(nums, target, False) - 1]
