Searching through a list for a specific item is a common task. To find someone's phone number, you must search through the telephone book looking for the person's name. To find the definition of a word, you search through the list of words contained in the dictionary.
As the examples above illustrate, the most common purpose of a search is to locate information related to the target of the search. In the first case, the target of the search is a person's name but the real purpose of the search is to find out the person's telephone number. In the second example, the target of the search is a specific word but the purpose of the search is to find the definition of the word.
Put into the context of computer programming, searches are commonly conducted on arrays where the location of an item is specified by its array index. Typically, search algorithms return the index at which the target is located and some other specified value if the target is not in the list. For example, in C++ and Java, the first element in an array is at index zero. A search routine might return a value of -1 to indicate an unsuccessful search. In other languages (such as Basic and Fortran) the first element in an array is at index 1 and a search routine might return a value of 0 after an unsuccessful search.
In some cases the index returned by the search algorithm is used to access a corresponding item in a parallel array. For example, peoples' names might be stored in one array and their phone numbers in the corresponding locations in a second array. The index returned by a search algorithm applied to the array of names would be used to access the corresponding telephone number.
In other cases, each item in the array is an entire multi-component entity (a record or an object). For example, each record might consist of a person's name and his or her telephone number. This array of records is searched to find a record with a specific name. The index returned by the search algorithm can then be used to retrieve the entire record thereby allowing access to the person's telephone number.
With a linear search you start at one end of the list and examine (or probe) each item one after the other until you find the target or you have examined the entire list. Each probe reduces the size of the unsearched portion of the list by one element. This is a very easy algorithm to implement and can be applied to any list (sorted or not). However, its linear traversal through the list makes it fairly slow, especially for large lists.
If the list is sorted, we can use a faster search algorithm. With a binary search, you begin in the middle of the list rather than at one end. If the target precedes the middle value then the entire second half of the list can be disregarded. Otherwise, the entire first half of the list can be disregarded. In either case, a single probe cuts the size of the unsearched portion of the list in half. The same process is applied to the remaining (unsearched) half of the list and so on. This algorithm is a little more difficult to implement and requires that the list be sorted. However, it is a much faster algorithm.
Click on this Search Algorithm Demo link to run a Java applet that visually illustrates these two search algorithms.
The efficiency of a search algorithm is related to how long it takes, on average, to complete a search operation. The efficiency is measured in the number of probes required to complete the search. The smaller the number of probes, the more efficient (faster) the search algorithm.
For a successful linear search, the number of probes depends on the location of the target but averages half the number of elements in the list. For an unsuccessful linear search, every element in the list will have been probed.
On average, the number of probes required for a binary search is the logarithm (base 2) of the number of elements in the list. Unlike the linear search, it doesn't make any difference whether the search is successful or not.
|Number of Probes
|n = the number of elements in the list
Click on this Search Efficiency Demo link to run a Java applet that visually compares the efficiencies of the linear and binary search algorithms.