二进制搜索长度问题：如果结束长度应该是数组的总长度或 array-1 的长度，则会感到困惑

Question

import java.util.*;
public class BinarySearc {

    public static int bsearch(int numbers[], int key) {
        int start = 0, end = numbers.length-1;

        while(start<=end) {
            int mid = (start + end)/2;

            // comparisions
            if(numbers[mid]==key) {
                return mid;
            }
            else if(numbers[mid]<key) {   
                start=mid+1;
            }
            else {
                end=mid-1;
            }
        }
        return -1;
    }
    public static void main(String args[]) {
        int numbers[] = {1, 2, 4, 6, 8, 10, 12, 14, 18, 20};
        Scanner sc = new Scanner(System.in) ;
        System.out.print("Enter value: ");
        int value = sc.nextInt();
        System.out.println("index for the value is: "+bsearch(numbers, value));
        sc.close();
    }
}

我正在为二进制搜索编写代码，这是我编写的代码，但最初我使用 start = 0 和 end = 数组的长度找到数组的中间，即 numbers.length 这似乎适用于这个数组，但是我看到许多在线代码示例将 end 的值用作（总数组长度 - 1），即这里的 numbers.length - 1。 有人可以解释为什么吗？

Answer 1

使用

numbers.length

恰好适用于您的代码测试用例，只是因为您在数组中找到了一个值而没有尝试搜索超出数组末尾的范围。如果您搜索例如

24

（大于数组中存在的任何值）同时将

end

初始化为

numbers.length

，然后当代码最终将

ArrayIndexOutOfBoundsException

的值分配给

numbers.length

和你访问数组。您应该始终将

mid

初始化为数组的长度减一，正如您在此处的代码中所具有的那样，因为这是数组中最后一个元素的索引。这将防止您的代码实现二进制搜索算法尝试访问不存在的数组元素。