**Algorithm Behavior Measurement:
Searching in a Sorted Linked List
**

Javadoc Documentation

This is available as a word processor file in RTF format (six pages)

We joked in class about doing a binary search within a sorted linked list: traverse half-way through the linked list before examining a data item; based on that, traverse a quarter-way through one of the two sublists, etc., etc. This is actually an algorithm that has some promise, as strange as it seems.

Like the array-based binary search, this algorithm will only
perform about log_{2}(*n*) comparisons. As to the list
traversal portion, that isn’t as wasteful as it might seem. If each time
we traverse, it’s only by half as much as the last time, then the total
traversals will have the form of *n*(1/2 + 1/4 + 1/8 + 1/16 +...), meaning
in the end that we only have to traverse *n* nodes, exactly the number we
would have to traverse for a linear search. Of course, the linear search
of a sorted list will end as soon as something *larger* than the sought
value is found, so there is an early exit available and on average you only need
to traverse half the list even on failure.

Either in your own implementation of a linked list of sorted
data, or in a stripped-down version with only the bare necessities, insert the
following two methods: `public Comparable linearSearch(Comparable sought)` and
`public Comparable binarySearch(Comparable sought)`. Develop your
program so that you can capture the number of comparisons performed, either by
including the logic within the search methods themselves or by using the
`class MyComparable` developed in the lectures. You will be able to
capture time through `System.nanoTime()`.

**Linear Search Algorithm**

Given `sought` as the value desired, you can find it by
doing a simple traversal of the sorted list: at each step, capture the
value returned by `compareTo()` regarding the item `sought` and
the data field of the list node — just call `compareTo()` once and retain
the value. If the value shows that the item `sought` comes earlier
in the list, it must not in fact be in the list so return the failure message, a
`null` reference. If the value is zero, return the data field of
the list node since you’ve found it. Otherwise continue the traversal.
If you get to the end without finding it, return the same failure message, a
`null` reference.

**Binary Search Algorithm**

The
`public Comparable binarySearch(Comparable sought)` method can use a
private recursive method to do all the work`:
private Comparable binarySearch(Node
left, int size, Comparable sought)`

The

{ return binarySearch(head, size, sought); } // or maybe binarySearch(head.next, size, sought)

__The Recursive Method__

If the size of the linked list segment is zero, return the `null` failure
indication. If the size of the linked list segment is exactly one, perform
the appropriate check and return either the failure indication or the `left`
node’s `data` field. Otherwise compute the size of the left sublist
(as `size/2`) and the size of the right sublist (as `size` minus the
size of the left sublist). Generate a `Node right = left`, then
move it to the front of the right sublist — you know exactly how many steps
that will take. As in the linear search algorithm, capture the value
returned by `compareTo()` regarding the item `sought` and the data
field of the `right` list node. If the value indicates that the
item `sought` is in the `left` sublist, make a recursive call passing
`left` and the computed length of that *sublist*. If the
value indicates that the item `sought` is in the `right` sublist, make a recursive call passing
`right.next` and the computed length of __that__ sublist ** minus one**,
since you have effectively discarded the node at `right`.
Otherwise you’ve found the item `sought`; return
`right.data`.

__Alternative to the Recursive Method__

For the student that wants a challenge: you don’t **need** a
recursive method. Do some reading about “tail recursion” and consider what
it means in the context of the above recursive algorithm.

**Driving Main**

If you wish, you may include the exercising `main` function as Sahni
does, or you can have it as a separate class. It is to allow for but not
require a command-line argument. Following the statement “`System.out.print("Size: )`”,
determine whether there is a command line argument (that is, if `args.length > 0`).
If so, parse `args[0]` as an integer, then complete the line on the screen
by printing out that size. If there is no command line argument, accept
the size from the `System.in`.

Generate a linked list containing even Integer objects from `2` up through
`2*size` (or MyComparable wrapper objects with those Integer objects).
The list will be the basis for your determining average algorithm performance
for both the linear search algorithm and the binary search algorithm. You
will determine both the average number of comparisons required and the average
time required in __microseconds__ (you will be using `System.nanoTime()`).

To determine the total comparisons and time to find, do each search on
each of the even numbers from 2 up through
`2*size`. For the averages, divide those numbers (*as doubles*)
by `size`. Within the loop, insure that the value returned by the
search is correct, that is, that the search succeeded and the correct value is
returned. If you are using MyComparable objects, do *not* compare
them directly as you check for correctness, but compare the objects returned by `getValue()`.
Alternatively, use the `freeCompare()` method rather than the c`ompareTo()` method.

To determine the total comparisons and time to fail, do each search on each
of the odd numbers from 1 up through (`2*size+1)`. For the
averages, divide those numbers (*as doubles*) by (`size+1`).
Within the loop, insure that the value returned by the search is correct, that
is, that the search failed.

*Hint:* to collect your data, capture the current time before you
start the loop and insure that the comparison count is zero. After you
exit the loop, capture the current time and the comparison count.

You are free to format your output in any fashion, *provided* that it is
easy to read. The instructor’s implementation generates the
following output.

Linear search with early exit, 4096 items 65.477 microseconds to find, with 2048.500 cmp 63.242 microseconds to fail, with 2049.000 cmp Binary search, 4096 items 17.085 microseconds to find, with 11.000 cmp 19.008 microseconds to fail, with 11.997 cmp

Once your program is working correctly, capture in a text file the results of running your program for the linked lists sizes 2048, 4096, 8192, and 16384. After that output, write a brief description of what you have observed.

In your main, also generate a
`java.util.LinkedList` with the same data and then capture the behavior of
`java.util.Collections.binarySearch()`
as well as your own linear search and binary search. You *will* have to
use the MyComparable class to capture the number of comparisons in this case.

This assignment must be submitted in ** working**
order by midnight Wednesday, 22 October. Submit a jar file with:

- your source file or files
- your text file as described above.
__IMPORTANT__: instructions on how to compile your program from the command line, noting specifically which file contains the driver.

The grader should be able to open your jar file, compile your
code, and run your program from the command line using **javac** and **java**
version 1.5 or greater (** so make sure you try this yourself before you
submit**). The grader will be testing both the command-line
specification of the list size and the user-dialog specification.