Implement the binary search algorithm in PHP.




Searching for an item in an array is quite a common task in programming. For instance, given the array [1, 2, 3], we might be interested in finding out whether it contains 4 in it or not.

Programatically, there are two ways of searching for a given item in an array.

One is the straightforward and elementary sequential approach, referred to as sequential search (and sometimes even as linear search). In this approach, we iterate over the entire array in search of the desired value. As soon as it is found, searching is ended.

All array methods in JavaScript that are meant to search for elements, i.e. indexOf() and includes(), use the sequential approach.

The second way of searching demonstrates an extremely clever and efficient searching technique. It's called binary search.

The name comes from the fact that searching proceeds by consecutively halving the given array and then discarding one half where the item to search is guaranteed to not exist. (Halving refers to 2, and that's what 'binary' means.)

At each stage in a binary search algorithm, the middle element of the array is compared with the item to search.

  • If it gives a match, we are done.
  • If not, then the array is split apart into two subarrays right at the position of the middle element. The next step is to repeat this exact same process on the subarray where the value might exist.

One crucial point to note is that binary search requires the underlying array to be sorted. The halving technique of the algorithm relies on the very fact that the array is sorted; that's essentially how we're able to determine the subarray where the searched item might exist.

Shown below is a demonstration of how binary search would find the number 500 in the array [1, 2, 9, 20, 60, 100, 101, 200, 500]:

In this exercise, you have to create a function binary_search() implementing the binary search algorithm described above.

The function should take in two arguments, the first one being the value to search while the second one being the array. It should return back true if the item exists, or else false.

Shown below is an example of the function's usage:


function binary_search($val, $arr) { /* ... */ }

$arr = [-1, 0, 0, 10, 50, 600];

var_dump(binary_search(10, $arr));
var_dump(binary_search(-1, $arr));
var_dump(binary_search(600, $arr));
var_dump(binary_search(100, $arr));
bool(true) bool(true) bool(true) bool(false)

Notice how the array $arr is sorted before we provide it to binary_search(). This is a vital step for the correctness of the algorithm.