# 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 &lt; iter_get_len[lenOverTwo]:
return binarySearch(iter_get_len[0: lenOverTwo], searchElement)
# searchElement  in the upper half
if searchElement &gt; 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 &lt; \$array[\$lengthOfArrayOverTwo]) {
# search the lower half
return  binarySearch(array_slice(\$array, 0, \$lengthOfArrayOverTwo), \$searchElement);
}

if (\$searchElement &gt; \$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);```