Computer Science
Binary Search
Linear Search
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
Repeat
If List[CurrentItem] = ItemSought
Then Found ← true
CurrentItem ← CurrentItem + 1
Until Found = True Or CurrentItem > Max
Binary Search
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
Repeat
midpoint ← (First + Last) DIV 2
IF List[midpoint] = ItemToFind
Then itemfound ← true
Else
IF First >= Last
Then searchfailed ← true
Else
IF List[midpoint] > ItemToFind
Then Last ← midpoint -1
Else First ← midpoint + 1
End If
End If
End If
Until itemfound OR searchfailed
End Procedure
This procedure can also be written recursively. A recursive version is used in the C# sample.