# Binary Search

Binary Search

HideShow resource information

## Pseudocode

Procedure BinarySearch

.............Repeat

...................Midpoint = First + Last / 2

........................If ItemSought = MidPoint

....................................Then ItemFound = True

.........................Else

....................................If MidPoint > ItemSought

....................................Then High = Midpoint - 1

....................................Else Low = Midpoint + 1

.........................End If

End.

1 of 2

## Normal Talk :)

• Find the middle value first by adding the low and the high and dividing by two.
• Check that the middle value isnt the one your looking for
• Check the value your looking for against the midpoint by seeing if its higher or lower
• If its higher, then you search the top half of the list, therefore elliminating the whole bottom half of the list and vice versa if it was lower.
• Keep doing this until the item is found

In terms of levels of complexity it is favourable over a Linear Search as that is O(n) where as a Binary search is O(LogN)

2 of 2