Binary search algorithm example with PHP

Tipo IT - author
Posted by : Darko Borojevic - contact me | go home

Binary search with PHP

Binary search is perhaps the most famous search algorithm for sorted arrays in software development. Let's take a look how a simple Binary Search algorithm might look like in PHP.

binary search code example

php binary search example

binary search - execution script

php binary search test code This algorithm is easy to implement and in the same time it is very fast. Binary Search is only possible on sorted arrays and that is probably it's only limitation. If there is a need for extracting data out of large sorted Arrays, Linear search just won't cut it, and this is where Binary search algorithm comes into play.

Binary search runs in logarithmic time in the worst case, making O(log n) comparisons, where n is the number of elements in the array, the O is Big O notation, and log is the logarithm. Binary search takes constant O(1) space, meaning that the space taken by the algorithm is the same for any number of elements in the array.
Logarithmic runtime can be seen as the opposite of an exponential runtime O(N2) in the same way dividing is the opposite of multiplying for example. Tehrefore, Binary search as an logarithmic runtime algorithm increases logarithmically with the number of elements in the array it has to search which is opposite to exponential increase.

O(N2) or exponential runtime, is common in algorithms that involve nested iterations over the array data sets. Deeper nested iterations can result in O(N3) or O(N4) and we can see how this can be a problem for Big Data and why logarithmic runtimes like Binary search which do the opposite, needs to be implemented.

Print article

Email article

Do you have a comment?