二分查找需要维护高低变量吗？

Question

我只使用 n 来实现它，因为无论如何低都会是 0，但是谈论“正确的算法方式”是否有必要存在高和低变量？我的实现：

public class ArrayBinarySearch {


    static int binarySearch(int[] a, int n, int key) {
        int mid = n / 2;

        if (key >= a[mid]) {
            for (int i = mid; i < n; i++) {
                if (a[i] == key)
                    return i;
            }
        }

        if (key < a[mid]) {
            for (int i = 0; i < mid; i++) {
                if (a[i] == key)
                    return i;
            }
        }

        return -1;
    }


    public static void main(String[] args) {
        int[] a = {
            1,
            2,
            3,
            6,
            8,
            10,
            29
        };
        int find = 29;

        int posn = binarySearch(a, a.length, find);

        if (posn == -1) {
            System.out.println("Not Found");
        } else {
            System.out.println("Found at " + (posn + 1));
        }

    }
}

Answer 1

您尚未实现适当的二进制搜索。

或者换一种说法：“真正的”二分搜索将多次递归搜索空间的一半，直到找到该值（或决定无法找到它）。

您的代码只将搜索空间减半一次：您决定数组的哪一半可能包含相关数据，然后对该一半进行线性搜索。

对于小型数组，您实现的代码将非常接近相同的性能（在某些极端情况下甚至可能会快一点），但对于大型数组，您将拥有比真正需要的更多的访问权限。

例如，如果您有一个包含 4000 个元素的数组，那么正确的二分查找最多需要 12 次比较才能找到该元素（因为每次比较都会将可能的位置数量减半）。

您的实现最多需要 2001 次比较才能找到元素。

并回答您的具体问题：是的，适当的二进制搜索需要两端，否则您将无法区分要搜索数组的哪一部分。它可能是阵列的前半部分，第二部分，第三部分 1/8，......

只有极少数所有可能的子集从数组的开头（或确切的中间）开始搜索。