Table of Contents

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

def binarySearch(iter_get_len, searchElement): ''' find search element in an iterable that has __get__ and __len__ ''' if len(iter_get_len) == 0: # searchElement Doesn't exist return False lenOverTwo = len(iter_get_len)//2 if iter_get_len[lenOverTwo] == searchElement: # searchElement found return True # searchElement in the lower half if searchElement < iter_get_len[lenOverTwo]: return binarySearch(iter_get_len[0: lenOverTwo], searchElement) # searchElement in the upper half if searchElement > iter_get_len[lenOverTwo]: return binarySearch(iter_get_len[lenOverTwo + 1:], searchElement) binarySearch([1, 2, 3, 4, 5], 1) == True binarySearch([1, 2, 3, 4, 5], 2) == True binarySearch([1, 2, 3, 4, 5], 7) == False

## Binary search in php

function binarySearch($array, $searchElement) { /* @param $array @param $searchElement @perform search using binary search for the $searchElement inside the $array */ $lengthOfArray = count($array); if ($lengthOfArray === 0) { return false; } $lengthOfArrayOverTwo = (int) ($lengthOfArray / 2); if ($array[$lengthOfArrayOverTwo] == $searchElement) { # searchElement found return True; } if ($searchElement < $array[$lengthOfArrayOverTwo]) { # search the lower half return binarySearch(array_slice($array, 0, $lengthOfArrayOverTwo), $searchElement); } if ($searchElement > $array[$lengthOfArrayOverTwo]) { # searchElement the upper half return binarySearch(array_slice($array, $lengthOfArrayOverTwo + 1), $searchElement); } } assert(binarySearch([1, 2, 3, 4, 5], 6) == False); assert(binarySearch([1, 2, 3, 4], 1) == True);