如何优化现有二分查找代码，满足O(logn)比较次数限制且禁用get读操作？

你提供的报错截图如下：

问题根因 #

现有代码的核心问题是单次循环最多调用2次compToValue比较方法，虽然时间复杂度仍为O(logn)，但比较次数的常数项是最优实现的2倍，直接触发了比较次数限制。

优化方案 #

核心优化点 #

• 单次循环仅调用1次compToValue，将返回结果缓存到临时变量后再做分支判断，直接砍掉一半的比较次数
• 修正mid计算逻辑，避免start+end超过int范围时的溢出问题
• 逻辑完全保持二分查找的正确性，不依赖任何get读操作，时间复杂度仍为严格O(logn)
• 去掉冗余的index变量，简化代码逻辑

优化后代码 #

public class MySearch {

    public static int search(MyArray array, int value) {
        int start = 0, end = array.length - 1;
        while(start <= end) {
            // 避免整数溢出的mid计算方式
            int mid = start + (end - start) / 2;
            // 单次循环仅调用一次比较方法，缓存结果避免重复调用
            int compRes = array.compToValue(mid, value);
            if(compRes == 1) {
                end = mid - 1;
            } else if(compRes == -1) {
                start = mid + 1;
            } else {
                return mid;
            }
        }
        // 未找到直接返回-1
        return -1;
    }
}

优化效果 #

优化后比较次数的常数项从2降至1，最坏场景下比较次数直接减少一半，完全符合O(logn)的次数要求，且没有引入任何读操作，逻辑和原有实现完全等价，无正确性问题。

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