二分查找进阶：如何精准定位排序数组的边界

题目背景

在 LeetCode 34 题中，给定一个按非递减顺序排列的整数数组 nums 和一个目标值 target，要求找出目标值在数组中的开始位置和结束位置。如果不存在，返回 [-1, -1]。

核心约束是算法的时间复杂度必须为 O(log n)，这意味着我们不能使用线性扫描，而必须利用有序数组的特性进行二分查找。

核心思路：二段性

二分查找的本质是利用数据的二段性。对于排序数组，我们可以将区间划分为两部分：一部分满足条件（例如小于 target），另一部分不满足条件（大于等于 target）。通过不断缩小搜索范围，我们就能定位到分界点。

本题需要找到两个边界：

1. 左边界：第一个大于等于 target 的位置。
2. 右边界：最后一个小于等于 target 的位置。

避免死循环的关键

在编写二分查找时，最容易踩坑的就是死循环。这通常发生在计算中点 mid 的方式不当，导致指针无法移动。

• 寻找左边界：当 mid 落在左侧区域时，我们需要向右收缩，即 left = mid + 1。此时 mid 的计算应偏向左侧，使用 left + (right - left) / 2。这样即使 left 和 right 相邻，mid 也会取 left，从而保证 left 能推进。
• 寻找右边界：当 mid 落在右侧区域时，我们需要向左收缩，即 right = mid - 1。此时 mid 的计算应偏向右侧，使用 left + (right - left + 1) / 2。否则若 mid 取 left，会导致 right 无法更新，陷入死循环。

此外，循环条件通常使用 while(left < right)。当左右指针相遇时，循环终止，此时只需验证该位置是否为目标值即可。如果在循环内继续处理 left == right 的情况且逻辑不当，极易引发死循环。

代码实现

下面是一个完整的 Java 实现。为了清晰起见，我将查找左右边界的逻辑拆分为两个独立的二分过程。

public int[] searchRange(int[] nums, int target) {
    int[] ret = new int[2];
    ret[0] = ret[1] = -1;
    
    if (nums.length == 0) {
        return ret;
    }

    // 1. 查找左边界：第一个 >= target 的位置
       , right = nums.length - ;
     (left < right) {
        
           left + (right - left) / ;
        
         (nums[mid] < target) {
            
            left = mid + ;
        }  {
            
            right = mid;
        }
    }
    
    
     (nums[left] != target) {
         ret;
    }
    ret[] = left;

    
    
    
    right = nums.length - ;
     (left < right) {
        
           left + (right - left + ) / ;
        
         (nums[mid] <= target) {
            
            left = mid;
        }  {
            
            right = mid - ;
        }
    }
    
    ret[] = left;
     ret;
}