解决无限有序数组查找元素时的Array Index Out Of Bound Error问题

参考Kunal Kushwaha的二分查找讲解视频实现了无限有序数组中查找元素的Java代码，但使用数组{1, 2, 4, 6, 8, 9, 10 , 13, 16, 19, 20 ,23, 27, 40, 42, 44}、目标值44测试时，出现Array Index Out Of Bound Error错误，请求排查并修正代码。

原代码如下：

public class InfiniteElement{
    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 6, 8, 9, 10 , 13, 16, 19, 20 ,23, 27, 40, 42, 44};
        int target = 44;
        System.out.print(findPos(arr, target));
    }
    
    static int findPos(int[] arr, int target){
        int start = 0;
        int end = 1;
        while(target > arr[end]){
            //temp will the new start
            int temp = end + 1;
        
            //instead of breaking the box we are multiplying
            //so that the chunk of boxes increase the window
            //it will help us to find the target in particular boxes
            // end = end + (end - start + 1) * 2; 
            // + 1 is because we are using the indices
            end = end + (end - start + 1) * 2;      
           start = temp;
        }
        return binarySearch(arr, target, start, end);
    }
    
    static int binarySearch(int[] arr, int target, int start, int end){
        while(start <= end){
            int mid = start + (end - start) / 2;
            if(arr[mid] == target){
                return mid;
            } else if(arr[mid] > target){
                end = mid - 1;
            } else{
                start = mid + 1;
            }
        }
        return -1;
    }
}

问题出在findPos方法的循环逻辑中：当目标值是数组的最后一个元素时，循环条件target > arr[end]会尝试不断扩展end的范围，但此时end会很快超过数组的最大下标（数组长度为16，最大下标是15），导致访问arr[end]时触发数组越界异常。

在扩展end之前，先判断end是否已经到达数组末尾；同时在循环条件中增加对end的边界检查，避免越界访问。具体修改点：

• 在while循环中，先检查end是否小于数组长度，再访问arr[end]
• 当end已经到达数组末尾时，直接跳出循环，将二分查找的右边界设为数组最后一个下标

public class InfiniteElement{
    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 6, 8, 9, 10 , 13, 16, 19, 20 ,23, 27, 40, 42, 44};
        int target = 44;
        System.out.print(findPos(arr, target));
    }
    
    static int findPos(int[] arr, int target){
        int start = 0;
        int end = 1;
        // 增加end的边界检查，避免越界访问arr[end]
        while(end < arr.length && target > arr[end]){
            int temp = end + 1;
            // 计算新的end时，确保不超过数组最大下标
            end = Math.min(end + (end - start + 1) * 2, arr.length - 1);
            start = temp;
        }
        // 如果end超出数组长度，将右边界设为数组最后一个下标
        end = Math.min(end, arr.length - 1);
        return binarySearch(arr, target, start, end);
    }
    
    static int binarySearch(int[] arr, int target, int start, int end){
        while(start <= end){
            int mid = start + (end - start) / 2;
            if(arr[mid] == target){
                return mid;
            } else if(arr[mid] > target){
                end = mid - 1;
            } else{
                start = mid + 1;
            }
        }
        return -1;
    }
}

1. 循环条件新增边界检查：while(end < arr.length && target > arr[end])，确保只有当end在数组范围内时才访问arr[end]，避免越界。
2. 限制end的最大值：用Math.min(end + (end - start + 1) * 2, arr.length - 1)计算新的end，保证end不会超过数组的最大下标。
3. 最终边界修正：在进入二分查找前，再次将end修正为数组最大下标，确保即使循环提前结束，右边界也是合法的。

内容的提问来源于stack exchange，提问作者UDAYA KRISHNAN.M