二分查找中low/high参数误用导致索引越界与性能异常该如何修复

二分查找的核心逻辑是通过不断缩小查找区间来定位目标元素，其中low和high两个参数分别标记当前查找区间的左右边界，很多错误都源于对这两个参数的边界控制不当。

常见参数误用场景及问题表现

1. 初始参数设置错误

很多开发者会把high的初始值设为数组长度，而不是数组长度减1，这会导致后续访问数组时出现索引越界。比如下面这段错误代码：

public static int binarySearch(int[] arr, int target) {
    int low = 0;
    // 错误：high初始设为arr.length，当low等于arr.length时访问arr[low]会越界
    int high = arr.length; 
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

2. 边界更新逻辑错误

另一种常见错误是在更新low和high时没有正确调整边界，导致查找区间无法缩小，出现死循环或者性能异常。比如下面的情况：

public static int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            // 错误：没有+1，当low=high时mid=low，区间无法缩小陷入死循环
            low = mid; 
        } else {
            // 错误：没有-1，同样会导致区间无法缩小
            high = mid; 
        }
    }
    return -1;
}

3. 循环条件与边界不匹配

如果循环条件用<而不是<=，同时high初始值设置为arr.length-1，会导致查找区间漏掉最后一个元素，出现查找结果错误的问题。

public static int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;
    // 错误：当low=high时循环终止，会漏掉arr[high]的判断
    while (low < high) { 
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

对应修复方案

1. 修正初始参数

首先确认high的初始值，如果数组索引从0开始，high应该初始化为arr.length - 1，代表最后一个有效元素的索引。修复后的初始参数设置如下：

int low = 0;
// 正确：high为最后一个元素的索引
int high = arr.length - 1;

2. 修正边界更新逻辑

当arr[mid]小于目标值时，目标只可能在mid右侧，因此low需要更新为mid+1；当arr[mid]大于目标值时，目标只可能在mid左侧，因此high需要更新为mid-1，确保区间不断缩小。修复后的更新逻辑如下：

if (arr[mid] < target) {
    // 正确：目标在右区间，左边界移到mid+1
    low = mid + 1;
} else {
    // 正确：目标在左区间，右边界移到mid-1
    high = mid - 1;
}

3. 匹配循环条件与边界

如果high初始值是arr.length-1，循环条件应该用<=，保证当low等于high时仍然会检查arr[low]这个元素。如果希望用<作为循环条件，需要将high初始值设为arr.length，同时调整边界更新逻辑，两种正确写法如下：

// 写法一：high初始为arr.length-1，循环条件用<=
public static int binarySearch1(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1;
}

// 写法二：high初始为arr.length，循环条件用<
public static int binarySearch2(int[] arr, int target) {
    int low = 0;
    int high = arr.length;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] < target) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return -1;
}

二分查找编写规范总结

为了避免low和high参数误用，编写二分查找时可以遵循以下规范：

• 明确区间定义：先确定查找区间是左闭右闭[low, high]还是左闭右开[low, high)，不要混合使用两种区间的定义
• 初始参数匹配区间：如果是左闭右闭区间，high初始为arr.length-1；如果是左闭右开区间，high初始为arr.length
• 循环条件匹配区间：左闭右闭区间用<=作为循环条件，左闭右开区间用<作为循环条件
• 边界更新匹配区间：左闭右闭区间更新时high要减1，左闭右开区间更新时high直接用mid即可
• mid计算避免溢出：不要用(low + high) / 2，改用low + (high - low) / 2，防止low+high溢出

按照上述规范编写二分查找代码，就可以有效避免low和high参数误用带来的索引越界和性能异常问题，保证算法的正确性和执行效率。

binary_searchlow_high_parameterindex_out_of_boundsperformance_optimization修改时间：2026-07-12 02:45:14