java - 当数组有奇数时如何使用二分查找？

Question

我正在使用 binarySearch，它适用于具有偶数索引的数组，但当数组具有奇数索引(长度)时，它会给出错误的结果。

我所做的一切:

public static int binarySearch(int[] list, int key) {

    int low = 0;
    int high = list.length - 1;
    while (high >= low) {
        int mid = (low + high) / 2;

        if (key < list[mid])
            high = mid - 1;
        else if (key == list[mid])
            return mid;
        else
            low = mid + 1;

    }
    return - 1;
}

输入:

int[] arr1 = {5, 6, 8, 9, 11, 12, 11, 50, 1, 3, 15, 121, 33, 16, 17, 18, 19};
int[] arr2 = {5, 6, 8, 9, 11, 12, 11, 50, 1, 3, 15, 121, 33, 16, 17, 18};

案例:

System.out.println(binarySearch(arr1, 12));
System.out.println(binarySearch(arr2, 12));

输出:

-1
5

我怎样才能在这两种情况下得到正确的输出？

Answer 1

二分查找只适用于有序数组

解决方案:添加 Arrays.sort(list)

public static int binarySearch(int[] list, int key) { 
    Arrays.sort(list);
    int low = 0;
    int high = list.length - 1;
    while (high >= low) {
        int mid = (low + high) / 2;
        if (key < list[mid]) high = mid - 1;
        else if (key == list[mid]) return mid;
        else low = mid + 1;
    } return - 1;
}