What is the Sherwood binary search algorithm in Java?

Question

I took my final for Java programming on Monday and passed it. I just got the graded hard copy today and my instructor said I should have used the Sherwood binary search algorithm instead of regular binary search. Does anyone have a template of this algorithm? I have tried searching on the web for it but only get the meaning of it and not an actual template or copy of the copy so I can run it.

Thanks necromancer I got it working and see why he may have wanted it.

Answer 1

The Sherwood algorithm is a modified version of the standard binary search. In search algorithms there is always a best case scenario and a worst case scenario that could happen. When performing a binary search there are always some locations that will require a fail in order to be checked. This number of fail checks will vary greatly depending on the number of elements that you are searching through.

The reasoning behind these fails is due to the fact of the core statement of a binary search is:

middle = (first + last) / 2;

With the Sherwood algorithm that standard structure is replaced by the concept of randomness. The core statement behind the Sherwood algorithm is:

middle = first + rand.nextInt(last - first + 1);

If you were searching a list of 1000 elements with the Sherwood algorithm and it picked the middle as 250th element. The value that you are searching for could be < the 250th element so in turn 75 percent of the elements in the list would be discarded rather than just 50 percent. At the same time the value could be greater than the 250th element and only 25 percent of the elements in the list would be discarded.

The concept is that the Sherwood algorithm will reduce the time of the worst case scenario and yet increase the time of the best case.

That's not to say that it is better than the binary search, but instead just showing another way of completing it. I believe that was the reasoning behind my professor's meaning because in his class he likes to see us think outside of the box and show multiple ways to get to one solution. You should always have multiple paths in case one path is blocked.

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.");
        }
    }