arrays - 对 BinarySearch 感到困惑

Question

可能重复：
Arrays.binarySearch 不能正常工作

根据我对 BinarySearch 的理解，如果在数组或集合中找不到元素，它只会返回一个插入点。

所以这段代码让我有点困惑：

import java.util.*;

public class LookinGlass {

    public static void main(String args[]){

        String[] asa = {"x", "c", "b", "d"};

        int x  = Arrays.binarySearch(asa, "b");

        System.out.println("Index is at " + x);

        Arrays.sort(asa);

        int y = Arrays.binarySearch(asa, "b");

        System.out.println(x + " " + y);
    }

}

当我打印出x时，为什么它说索引为-1，而数组中显然存在“b”并且可以找到？

谢谢

Answer 1

因为二进制搜索不适用于未排序的数组。当您看到一个更大的元素时，您会断定搜索的项目不在数组中。

Answer 2

二分搜索算法假定它正在查看按升序排序的数据，在您第一次调用数组时：

 String[] asa = {"x", "c", "b", "d"};

未排序。因此，Arrays.binarySearch(asa, "b");调用正在返回-1，因为它无法"b"使用二分搜索算法在您的数组中找到。

Answer 3

如果你认为二分搜索的工作方式很接近，然后试着想象如果你在一个未排序的列表上运行二分搜索会发生什么，那么它为什么不起作用应该会很明显。

如果仍有疑问，请实现您自己的二进制搜索并逐步完成。