binary search algorithm in python , and php

Binary search algorithm

Binary search is used to find if a sorted iterable , that can be indexed , contains an element in O(nlog(n)) . It is faster than a a sequential search , where we can check if an element exists in a sorted iterable in O(n).

The binary search algorithm consists of :

  • finding the middle of the iterable
  • comparing the value that we want to search for , with the value located at the middle .
  • if the value we are searching for , is equal to the value located at the middle of the iterable , we have found the element , so we stop the search , and we return true .
  • if the value we are searching for , is larger than the value located at the middle of the iterable , we must search the middle + one of the iterable till its end , as this value will be located in the upper half .
  • if the value we are searching for , is smaller than the value located at the middle of the iterable , we must search from the start of the iterable , to the middle -one, as the value will be located in the lower half.
  • if the length of the iterable is zero , then the value doesn’t exist , and return false

Binary search in python

Binary search in php

Originally published at https://twiserandom.com on July 11, 2020.