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

Linear Search In C#

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.

Binary Search In C#