二分查找与变形问题

一、标准二分查找

1.1 前提条件

• 数组有序
• 支持随机访问

1.2 标准实现

public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

1.3 防溢出

// 不推荐
int mid = (left + right) / 2;  // 可能溢出

// 推荐
int mid = left + (right - left) / 2;
// 或
int mid = (left + right) >>> 1;

二、查找边界

2.1 查找第一个等于target的位置

public int findFirst(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int res = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            res = mid;
            right = mid - 1;  // 继续向左找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return res;
}

2.2 查找最后一个等于target的位置

public int findLast(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    int res = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) {
            res = mid;
            left = mid + 1;  // 继续向右找
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return res;
}

2.3 查找第一个大于等于target的位置

public int lowerBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

2.4 查找第一个大于target的位置

public int upperBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

三、旋转数组查找

3.1 问题

有序数组旋转后，查找target。

public int searchRotated(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        
        // 判断哪一半有序
        if (nums[left] <= nums[mid]) {  // 左半有序
            if (nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        } else {  // 右半有序
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

四、二分查找的泛化应用

4.1 求平方根

public int mySqrt(int x) {
    int left = 0, right = x;
    int res = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        long square = (long) mid * mid;
        if (square == x) return mid;
        if (square < x) {
            res = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return res;
}

4.2 查找峰值

public int findPeakElement(int[] nums) {
    int left = 0, right = nums.length - 1;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[mid + 1]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

五、总结

二分查找的精髓在于确定搜索区间的不变性：

• left <= right：闭区间，最后 left = right + 1
• left < right：左闭右开，最后 left = right

掌握边界处理和变形问题，二分查找可以解决远超”查找元素”的各类问题。