什么是Java中的Sherwood二进制搜索算法？

Question

我在周一参加了Java编程,并通过了它.我今天刚拿到了分级硬拷贝,我的导师说我应该使用Sherwood二进制搜索算法而不是常规二进制搜索.有没有人有这个算法的模板？我尝试在网上搜索它,但只获得它的含义,而不是实际的模板或副本的副本,所以我可以运行它.

感谢死灵法师我让它工作,看看为什么他可能想要它.

Answer 1

舍伍德算法是标准二分搜索的修改版本。在搜索算法中，总是存在可能发生的最好情况和最坏情况。执行二分查找时，总会有一些位置需要失败才能检查。根据您正在搜索的元素数量，失败检查的数量将有很大差异。

这些失败背后的原因是二分搜索的核心语句是：

中间=（第一个+最后一个）/ 2；

使用 Sherwood 算法，标准结构被随机性概念取代。Sherwood算法背后的核心说法是：

中间 = 第一个 + rand.nextInt(最后 - 第一个 + 1);

如果您使用 Sherwood 算法搜索包含 1000 个元素的列表，它会选择中间的元素作为第 250 个元素。您正在搜索的值可能小于第 250 个元素，因此列表中 75% 的元素将被丢弃，而不仅仅是 50%。同时该值可能大于第 250 个元素，并且列表中只有 25% 的元素会被丢弃。

这个概念是舍伍德算法将减少最坏情况的时间，同时增加最好情况的时间。

这并不是说它比二分搜索更好，而只是展示了另一种完成它的方法。我相信这就是我教授的意思背后的原因，因为在他的课堂上，他喜欢看到我们跳出框框思考，并展示多种方法来获得一个解决方案。您应该始终拥有多条路径，以防其中一条路径被阻塞。

public static void sherwoodSearch(int[ ] array, int value)
    {
        int first, last, middle, position, count;
        boolean found;

        //set the inital values.
        first = 0;
        last = array.length-1;
        position = -1;
        found = false;
        count =1;
        Random rand = new Random();
        //search for the value
        while (!found && first <= last)
        {
            count++;
            middle = first + rand.nextInt(last - first + 1);
            if (array[middle] == value)
            {
                found = true;
                position = middle;
            }
            else if (array[middle] > value)
                last = middle -1;
            else
                first = middle + 1;
            if (first <= last)
            {
                System.out.println("The number was found in array subscript" + position);
                System.out.println("The sherwood search found the number after " + count +
                    " comparisons.");

            }
            else
                System.out.println("Sorry, the number is not in this array.  The sherwood search made "
                    +count  + " comparisons.");
        }
    }