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

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);

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