Java字符串数组二分查找方法返回索引偏移1位的问题排查

我在类中实现了以下binarySearch方法，用于在String类型的employee数组中查找指定元素searchElement，但方法返回的索引始终比目标元素的实际索引小1。比如目标元素在索引4时，方法返回3。

public static int binarySearch(String employee[], String searchElement){

    int startingIndex = 0;
    int lastIndex = employee.length-1;

    while(startingIndex <= lastIndex){

        int midIndex= startingIndex + (lastIndex) / 2;
        int result = searchElement.compareTo(employee[midIndex]);

        if(result == 0)
            return midIndex;
        else if(result>0)
            startingIndex = midIndex + 1;
        else
            lastIndex = midIndex - 1;
    }
    return -1;
}

我期望该方法能返回目标元素的实际索引。

问题原因与修复方案 #

问题出在中间索引的计算逻辑上，当前的midIndex计算公式是错误的：

int midIndex= startingIndex + (lastIndex) / 2;

正确的二分查找中间索引计算应该是通过起始索引和结束索引的差值来偏移，避免起始索引不为0时的计算偏差：

int midIndex = startingIndex + (lastIndex - startingIndex) / 2;
// 等价写法：int midIndex = (startingIndex + lastIndex) / 2;

举个例子：当startingIndex=2、lastIndex=5时，你的公式得到2+5/2=4，而正确的中间索引应该是(2+5)/2=3，这种偏差会导致查找过程提前偏移，最终返回比实际索引小1的结果。

修正后的完整方法：

public static int binarySearch(String employee[], String searchElement){

    int startingIndex = 0;
    int lastIndex = employee.length-1;

    while(startingIndex <= lastIndex){

        int midIndex = startingIndex + (lastIndex - startingIndex) / 2;
        int result = searchElement.compareTo(employee[midIndex]);

        if(result == 0)
            return midIndex;
        else if(result>0)
            startingIndex = midIndex + 1;
        else
            lastIndex = midIndex - 1;
    }
    return -1;
}

另外需要注意：二分查找的前提是数组必须按字典序排序，如果你的employee数组未排序，也会导致查找结果异常。

内容的提问来源于stack exchange，提问作者Abdullah Sultan