# Computer ScienceBinary 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#