The linear search is the simplest method to search for items stored in an unsorted list. The technique involves comparing the search item with each item in the list until either a match is found or the end of the list is reached.
The algorithm in pseudocode for a linear search is as follows,
CurrentItem ← 1
Found ← false
If List[CurrentItem] = ItemSought
Then Found ← true
CurrentItem ← CurrentItem + 1
Until Found = True Or CurrentItem > Max
The linear search is not particularly efficient when searching a sorted array. The binary search works by comparing the item you want to find with the item stored at the midpoint of the list. If the item should come before the item at the midpoint, the second half of the list need not be searched. The midpoint of the the first part of the list would then be compared with the search item and a similar process followed. By comparing the item with ever-shrinking lists, the binary search requires very few comparisons to either find an item or establish that it is not in the list.
Iterative Binary Search
Procedure BinarySearch(List, First, Last, ItemToFind)
itemfound ← false
searchfailed ← false
midpoint ← (First + Last) DIV 2
IF List[midpoint] = ItemToFind
Then itemfound ← true
IF First >= Last
Then searchfailed ← true
IF List[midpoint] > ItemToFind
Then Last ← midpoint -1
Else First ← midpoint + 1
Until itemfound OR searchfailed
This procedure can also be written recursively. A recursive version is used in the C# sample.