作者：labuladong
链接：https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/
来源：力扣（LeetCode）
原文解释的很好，推荐阅读。二分查找的细节就是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] 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
