原文解释的很好，推荐阅读。二分查找的细节就是while 条件是< 还是 <=,更新right=mid还是mid+1，可以用区间开闭来理解。
while left < right 意味着 搜索区间是 [left,right)左闭右开，
while left <= right 意味着 搜索区间是 [left,right]左闭右闭。
这个搜索空间也决定了后面的更新。以左边界为例，如果使用 left<=right闭区间形式，
初始化left,right = 0,len(nums)-1 对应[0,len(nums)-1]
那么 nums[mid] > target 时，right = mid-1，搜索区间变为[left,mid-1]
nums[mid] == target时，right = mid-1，搜索区间为[left,mid-1],继续向左压缩。
nums[mid] < target时，left = mid+1, 搜索空间为[mid+1,right]。
而如果使用 left< right 左闭右开形式，初始化left,right = 0,len(nums) 对应[0,len(nums))
nums[mid] > target 时 , right = mid，搜索区间变为[left,mid)
nums[mid] == target时，right = mid，搜索区间为[left,mid),继续向左压缩。
nums[mid] < target时， left = mid+1, 搜索空间为[mid+1,right)。
给出二分查找模板，包括：二分查找目标值，左边界，右边界。
（Java和Python版本）
直接查找目标值很简单，
nums[mid]<target，压缩左边 left = mid +1
nums[mid]>target,压缩右边 right = mid -1
nums[mid]==target , 返回 mid
查找左边界的前两部分类似，但nums[mid]==target时要继续压缩右边界，锁定左边界，最后返回左边界。注意处理越界情况。
查找右边界同理。
int binary_search(int[] nums, int target) { int left = 0, right = nums.length - 1; while(left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if(nums[mid] == target) { // 直接返回 return mid; } } // 直接返回 return -1; } int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别返回，锁定左侧边界 right = mid - 1; } } // 最后要检查 left 越界的情况 if (left >= nums.length || nums[left] != target) return -1; return left; } int right_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别返回，锁定右侧边界 left = mid + 1; } } // 最后要检查 right 越界的情况 if (right < 0 || nums[right] != target) return -1; return right; }
class Solution: def binary_search(self,nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 elif nums[mid] > target: right = mid - 1 elif nums[mid] == target: return mid return -1 def left_bound(self,nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 elif nums[mid] > target: right = mid - 1 elif nums[mid] == target: right = mid -1 if left >= len(nums) or nums[left] != target: return -1 return left def right_bound(self,nums: List[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 elif nums[mid] > target: right = mid - 1 elif nums[mid] ==target: left = mid + 1 if right < 0 or nums[right] != target: return -1 return right
