如何修改二分搜索实现k近似排序数组的元素查找？

给定一个非负整数数组，满足以下特性：

• 数组中除零以外的元素均有序；
• 连续零的数量最多为k；
• 移除所有零后得到的正整数数组是有序的。

示例数组：3 0 0 4 7 9 0 0 0 0 11 15 0 19 20 0 0 31 40 0（对应k=4）

需要实现函数kAlmostSearch(int[] a, int num)，其中k是未知常数（仅知k小于数组长度），要求时间复杂度为O(k*log n)（k=0时退化为O(log n)的二分搜索）。目前已实现closestLeft和closestRight函数用于查找指定位置最近的非零元素下标，但在二分搜索过程中，当mid位置为零且左右均存在非零元素时，不知道如何调整搜索指针，现有代码如下：

public static int closestLeft(int a[], int index){
    int current=index;
    while(current>=0 && a[current]==0){
        current--;
    }
    if(current<0){
        return -1;
     }
    return current;
}

public static int closestRight(int a[], int index){
    int current=index;
    while(current<=a.length-1 && a[current]==0){
        current++;
    }
    if(current>a.length-1){
        return -1;
    }
    return current;
}

public static int kAlmostSearch(int a[], int num){
    int lo=0, hi=a.length-1, mid, closestLeft, closestRight;
    while(lo<=hi){
        mid=(lo+hi)/2;
        if(a[mid]==0){
            if(closestLeft(a,mid)==-1){
                mid=closestRight(a,mid);
            }else if(closestRight(a,mid)==-1){
                mid=closestLeft(a,mid);
            }else{
                /*how am I supposed to move here*/
            }
         }
        if(a[mid]==num){
            return mid;
        }
        if(a[mid]<num){
            lo=mid+1;
        }else{
            hi=mid-1;
        }
    }
    return -1; // 原代码缺少未找到的返回值
}

当mid为零且左右都有非零元素时，需要通过左右最近非零元素的大小判断目标值的存在区间：

1. 获取左边最近非零元素的下标leftIdx和值leftVal，右边的rightIdx和rightVal。
2. 若num < leftVal：目标值在左半区间，将hi设为leftIdx - 1。
3. 若num > rightVal：目标值在右半区间，将lo设为rightIdx + 1。
4. 若leftVal < num < rightVal：目标值不存在，直接返回-1（因为移除零后的数组有序，中间零区域不可能包含目标值）。
5. 若num等于leftVal或rightVal，直接返回对应下标。

同时注意：不要直接修改mid的值，而是调整lo和hi来缩小搜索范围，避免逻辑混乱；原代码缺少未找到目标值时的返回语句，需要补充。

修改后的完整函数：

public static int closestLeft(int a[], int index){
    int current=index;
    while(current>=0 && a[current]==0){
        current--;
    }
    return current < 0 ? -1 : current;
}

public static int closestRight(int a[], int index){
    int current=index;
    while(current<=a.length-1 && a[current]==0){
        current++;
    }
    return current > a.length-1 ? -1 : current;
}

public static int kAlmostSearch(int[] a, int num){
    int lo = 0, hi = a.length - 1;
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        int currentMid = mid;
        
        // 处理mid为0的情况
        if(a[mid] == 0){
            int leftIdx = closestLeft(a, mid);
            int rightIdx = closestRight(a, mid);
            
            // 左边无元素，只能看右边
            if(leftIdx == -1){
                if(rightIdx == -1){ // 全零区间
                    return -1;
                }
                currentMid = rightIdx;
            } 
            // 右边无元素，只能看左边
            else if(rightIdx == -1){
                currentMid = leftIdx;
            } 
            // 左右都有非零元素
            else {
                int leftVal = a[leftIdx];
                int rightVal = a[rightIdx];
                
                if(num == leftVal){
                    return leftIdx;
                }
                if(num == rightVal){
                    return rightIdx;
                }
                if(num < leftVal){
                    hi = leftIdx - 1;
                    continue; // 直接进入下一轮循环，重新计算mid
                }
                if(num > rightVal){
                    lo = rightIdx + 1;
                    continue; // 直接进入下一轮循环，重新计算mid
                }
                // 介于leftVal和rightVal之间，不存在目标值
                return -1;
            }
        }
        
        // 处理当前mid（或替换后的currentMid）的非零情况
        if(a[currentMid] == num){
            return currentMid;
        }
        if(a[currentMid] < num){
            lo = currentMid + 1;
        } else {
            hi = currentMid - 1;
        }
    }
    // 遍历完未找到目标值
    return -1;
}

每次调用closestLeft和closestRight最多遍历k个连续零，时间复杂度为O(k)；二分搜索的循环次数为O(log n)，因此整体时间复杂度为O(k*log n)，符合要求。

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