大数组元素查找优化方案报错求助：二分查找提交失败问题

我在CodinGame完成一道简单题，需求是判断某个元素是否存在于数组中。第一版用线性遍历的朴素方案能正常运行，但机器判定未优化；第二版尝试二分查找优化，本地测试结果正确，但提交后在空数组、超大数组等场景完全错误，求帮忙排查问题。

第一版朴素线性遍历方案 #

public static boolean check(int[] ints, int k) {
    boolean res = false;

    for(int i : ints){
        if(i == k){
            res = true;
            break;
        }
    }
    return res;
}

第二版二分查找代码（存在问题） #

static boolean exists(int [] ints, int k){
    boolean res = false;
    int first = 0;
    int last = ints.length;
    int mid = (first + last)/2;
    while(first <= last){
        if( ints[mid] < k){
            first = mid +1;
        }else if (ints[mid] == k){
            res = true; 
            break;
        }else{
            last = mid -1;
        }
     mid = (first + last)/2;
     }
     if(first > last){
        res = false;
     }
     return res;
 }

问题分析与修复 #

核心问题点： #

• 空数组直接越界：当ints为空时，ints.length=0，last=0，mid=0，此时访问ints[mid]会触发数组索引越界异常。
• 初始边界错误：数组索引范围是0到ints.length-1，你把last初始化为ints.length，会导致mid可能等于ints.length，访问ints[mid]越界。
• mid计算时机错误：在循环外先计算mid，且每次循环结束后更新mid，当first > last时（比如first=1、last=0），(first+last)/2会得到负数或超出数组范围的值，引发越界。
• 冗余逻辑：最后判断first>last时设置res=false完全多余，因为res初始值就是false，未找到元素时保持初始值即可。

修复后的二分查找代码 #

static boolean exists(int[] ints, int k) {
    // 空数组直接返回false
    if (ints == null || ints.length == 0) {
        return false;
    }

    int first = 0;
    int last = ints.length - 1;

    while (first <= last) {
        // 用first + (last - first)/2避免超大数组时first+last溢出
        int mid = first + (last - first) / 2;
        if (ints[mid] < k) {
            first = mid + 1;
        } else if (ints[mid] == k) {
            return true; // 找到直接返回，无需继续循环
        } else {
            last = mid - 1;
        }
    }

    // 循环结束未找到，返回false
    return false;
}

额外优化：用first + (last - first)/2代替(first+last)/2，避免超大数组中first+last超出int范围导致溢出。

内容的提问来源于stack exchange，提问作者Unknown kind Panda