二分查找程序无法正确输出不存在的查找键对应负索引问题

问题根因 #

二分查找递归终止（即查找键不存在）时，hi变量的值才是「小于查找键的最大元素的下标」，你当前代码错误返回了-lo，返回值会比预期小1，才会出现查找10返回-10而非-9的问题。

修复方案 #

仅需要修改search方法终止递归时的返回值即可，将原来的：

return -1*lo;

修改为：

return -1 * hi;

修复后完整代码 #

public class BinarySearch{

    public static int search(int key, int [] a, int lo, int hi)
    {  
        int n = a.length;
        
        if (hi >= lo) 
        {
            int mid = lo + (hi - lo) / 2;
            if ((mid == n-1 || key < a[mid+1]) && a[mid] == key) 
                return mid;
            else if (key < a[mid]) 
                return search(key, a, lo, (mid-1));
            else 
                return search(key, a, (mid+1), hi);
        }   
        return -1 * hi;
    }
    public static void main (String [] args)
    {
        In in = new In(args[0]);
        
        int key = Integer.parseInt(args[1]);
        
        int [] a = in.readAllInts(); 
        
        System.out.println(search(key, a, 0, a.length-1));

    }
}

验证结果 #

• 执行java BinarySearch input.txt 10，输出-9，符合预期
• 执行java BinarySearch input.txt 6，输出6，符合预期
• 查找大于所有元素的键12，输出-10，对应a[10]=11是小于12的最大下标，符合规则
• 查找小于所有元素的键1，输出1，对应不存在小于1的元素，逻辑自洽

内容的提问来源于stack exchange，提问作者gizmo.java