Binary Search | 二分查找

二分查找的边界条件之所以容易让人困惑，是因为循环的终止条件、搜索区间的定义以及左右边界的更新方式三者必须严格保持一致。如果其中一个地方搞错了，就会导致死循环或者漏查元素。

在开始之前，请记住一个原则：区间不变性。 也就是说，你定义的 [left, right] 或者 [left, right)，在每一轮循环开始的时候，都要保证目标值（如果存在）一定在这个范围内。边界更新的目的，就是根据中间值的比较结果，缩小区间但保持这个性质。

闭区间写法 [left, right] #

这是最直观的写法。

• 区间定义：left 和 right 都是有效的数组下标，即搜索范围包含两端。
• 循环条件：left <= right。因为当 left == right 时，区间 [left, right]内还有一个元素，需要继续查找。
• 右边界更新：right = mid - 1。因为 mid 已经检查过了，且比目标值大（假设场景），所以新的右边界应该是 mid 前面的那个位置。
• 左边界更新：left = mid + 1。同理，mid 已经检查过，新的左边界是 mid 后面的位置。

def binary_search_closed(nums, target):
   if not nums:
       return -1
   
   left, right = 0, len(nums) - 1
   
   while left <= right:  # 注意是 <=
       mid = left + (right - left) // 2  # 防止溢出
       if nums[mid] == target:
           return mid
       elif nums[mid] < target:
           left = mid + 1  # mid 在左边，排除它
       else:
           right = mid - 1 # mid 在右边，排除它
           
   return -1

左闭右开区间写法 [left, right) #

这是 C++ STL 标准库中常用的写法，也是很多算法题解中常见的风格。

• 区间定义： left 是有效的下标， right 是无效的下标（即搜索范围不包含 right ）。
• 循环条件： left < right 。因为当 left == right 时，区间 [left, right) 已经为空，没有元素了。
• 右边界更新： right = mid 。因为当前区间不包含 right ，所以将 right 设置为 mid ，相当于把新搜索区间设置为 [left, mid) ，正好排除了已经检查过的 mid 。
• 左边界更新： left = mid + 1 。因为 left 是包含的，要排除 mid ，就得从 mid + 1 开始。

def binary_search_left_closed(nums, target):
    if not nums:
        return -1
    
    left, right = 0, len(nums)  # 注意 right 是 len(nums)，不包含
    
    while left < right:  # 注意是 <
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1   # 进入区间 [mid+1, right)
        else:
            right = mid      # 进入区间 [left, mid)
            
    return -1

左开右闭区间写法 (left, right] #

这种写法相对少见，主要为了对称性理解。由于数组下标从 0 开始，左开区间需要处理 -1 这个边界。

• 区间定义： left 是无效下标（不包含）， right 是有效下标（包含）。
• 初始化： left = -1 ， right = len(nums) - 1 。
• 循环条件： left < right 。因为当 left + 1 == right 时，区间 (left, right] 内还有一个元素（即 right 本身），所以不能取等号。
• 右边界更新： right = mid - 1 。因为 mid 被检查过，且右区间是闭的，所以新右边界要跳过 mid 。
• 左边界更新： left = mid 。因为左区间是开的，将 left 更新为 mid ，相当于新的区间不包含旧的 left ，但包含 mid 吗？等等，这里容易混淆，我们需要仔细推演。实际上，这种写法为了保证区间不变性，更新规则与闭区间相反

def binary_search_right_closed(nums, target):
    if not nums:
        return -1
    
    left, right = -1, len(nums) - 1  # 左开右闭 (left, right]
    
    while left < right:
        # 因为左开，为了确保 mid 落在有效区间内，通常需要向上取整
        # 否则可能陷入死循环
        mid = left + (right - left + 1) // 2  
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid      # target 在右边，更新左边界为 mid (开区间)
        else:
            right = mid - 1 # target 在左边，更新右边界为 mid-1 (闭区间)
            
    return -1

为什么 mid 要向上取整？ 因为在左开右闭的写法中，如果只剩两个元素（例如 left = 0 , right = 1 ，实际指向索引1），向下取整得到 mid = 0 。如果 nums[0] < target ，我们会执行 left = mid = 0 ，区间仍然是 (0, 1] ，导致死循环。向上取整得到 mid = 1 ，就能避免这个问题。

开区间写法 (left, right) #

这种写法极端情况更多，主要用于理论探讨，实际工程中很少使用。

• 区间定义： left 和 right 都是无效下标。
• 初始化： left = -1 ， right = len(nums) 。
• 循环条件： left + 1 < right 。表示区间内至少有一个元素时继续循环。
• 边界更新：
  • left = mid (排除 mid 左侧)
  • right = mid (排除 mid 右侧)

def binary_search_open(nums, target):
    if not nums:
        return -1
        
    left, right = -1, len(nums)  # 开区间 (left, right)
    
    while left + 1 < right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid   # 进入区间 (mid, right)
        else:
            right = mid  # 进入区间 (left, mid)
            
    return -1

总结与对比 #

区间类型	区间表示	初始化	循环条件	左边界更新	右边界更新	中间值取法
闭区间	[left, right]	0, len-1	left <= right	left = mid + 1	right = mid - 1	向下取整
左闭右开	[left, right)	0, len	left < right	left = mid + 1	right = mid	向下取整
左开右闭	(left, right]	-1, len-1	left < right	left = mid	right = mid - 1	向上取整
开区间	(left, right)	-1, len	left + 1 < right	left = mid	right = mid	向下取整

为什么边界难判断？ 因为只要记住一条原则，就可以推导出所有写法：确保每次循环后，搜索区间在缩小的同时，仍然覆盖所有可能包含目标值的元素，并且不会重复检查已排除的元素。 如果你忘了这个原则，只死记硬背代码，就很容易出错。

Last modified on 2026-03-15