Binary Search

Algorithm

Given a sorted list:

  1. Select the element in the middle of the list.
  2. Compare the middle element to the element to be searched
    1. If the element is smaller than the middle element, repeat at 1. with left partition.
    2. If the element is greater than the middle element, repeat at 1. with right partition.
    3. If the element is equal to the middle element, the element has been found so stop.

Performance

  • Worst case: $O(log(n))$
  • Best case: $O(1)$
  • Average case: $O(log(n))$
  • Space complexity: $O(1)$

Implementations


fuss/algorithms/searching/binary_search.txt ยท Last modified: 2017/02/22 18:30 (external edit)

Access website using Tor Access website using i2p


For the copyright, license, warranty and privacy terms for the usage of this website please see the license, privacy and plagiarism pages.