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

Comments

No comments have yet been made

Similar Computing resources:

See all Computing resources »See all resources »