How to: Create a Binary Search in PHP

Are you looking to improve the performance of your PHP code by implementing a binary search algorithm? Binary search is a powerful technique for finding specific values in sorted arrays, and it can be a great tool for optimizing your code. In this article, we’ll show you how to create a binary search function in PHP.

What is a Binary Search?

A binary search is an algorithm for finding a specific value in a sorted array. The basic idea behind binary search is to divide the array in half repeatedly until the value is found. This approach is much faster than searching the array linearly, which would require checking every element in the array.

Binary search is often used in computer science and programming because it has a time complexity of O(log n), which means that the time it takes to search the array grows logarithmically with the size of the array. In contrast, linear search has a time complexity of O(n), which means that the time it takes to search the array grows linearly with the size of the array.

Implementing a Binary Search in PHP

To implement a binary search in PHP, you’ll need to write a function that takes an array and a value to search for as arguments. The function will then divide the array in half repeatedly until the value is found or the array is exhausted.

Here’s an example implementation of a binary search function in PHP:

function binarySearch($array, $value) {
  $low = 0;
  $high = count($array) - 1;
  
  while ($low <= $high) {
    $mid = floor(($low + $high) / 2);
    
    if ($array[$mid] == $value) {
      return $mid;
    } elseif ($array[$mid] > $value) {
      $high = $mid - 1;
    } else {
      $low = $mid + 1;
    }
  }
  
  return -1;
}

Let’s break down how this function works. First, we initialize $low to 0 and $high to the index of the last element in the array. We then enter a loop that continues until $low is greater than $high.

In each iteration of the loop, we calculate the index of the middle element of the array using the floor function. We then compare the value at the middle index to the value we’re searching for. If the middle value is equal to the search value, we’ve found our value and we return the index of the middle value.

If the middle value is greater than the search value, we update $high to be one less than the middle index. This is because we know that the value we’re searching for must be in the lower half of the remaining array.

If the middle value is less than the search value, we update $low to be one more than the middle index. This is because we know that the value we’re searching for must be in the upper half of the remaining array.

If we’ve exhausted the array without finding the search value, we return -1 to indicate that the value was not found.

Using the Binary Search Function

Now that we have a binary search function, let’s see how we can use it in our PHP code. First, we need to create a sorted array to search:

$array = [1, 3, 5, 7, 9, 11, 13, 15];

We can then call the binarySearch function to search for a specific value in the array:

$index = binarySearch($array, 7);

If the value is found in the array, $index will be set to the index of the value (in this case, 3). If the value is not found, $index will be set to -1.

You can use the binary search function in any PHP application where you need to search a sorted array for a specific value. It can be particularly useful in large arrays where linear search would be too slow.

Optimizing the Binary Search Function

While the basic binary search function we’ve implemented is effective, there are a few ways to optimize it further. For example, you can use recursion instead of a loop to implement the binary search algorithm.

Here’s an example implementation of a recursive binary search function in PHP:

function binarySearchRecursive($array, $value, $low = 0, $high = null) {
  if ($high === null) {
    $high = count($array) - 1;
  }
  
  if ($low > $high) {
    return -1;
  }
  
  $mid = floor(($low + $high) / 2);
  
  if ($array[$mid] == $value) {
    return $mid;
  } elseif ($array[$mid] > $value) {
    return binarySearchRecursive($array, $value, $low, $mid - 1);
  } else {
    return binarySearchRecursive($array, $value, $mid + 1, $high);
  }
}

This function works similarly to the previous implementation, but it uses recursion to divide the array in half. The function takes an additional two arguments, $low and $high, which define the range of the array to search.

The function first checks if $high is null. If it is, we set it to the index of the last element in the array. We then check if $low is greater than $high. If it is, we return -1 to indicate that the value was not found.

We then calculate the index of the middle element and compare it to the search value. If the middle value is equal to the search value, we return the index of the middle value.

If the middle value is greater than the search value, we recursively call binarySearchRecursive with $low and $mid - 1. If the middle value is less than the search value, we recursively call binarySearchRecursive with $mid + 1 and $high.

This implementation of the binary search algorithm may be slightly more efficient than the previous one because it avoids the overhead of the loop construct.

Conclusion

In this article, we’ve shown you how to implement a binary search function in PHP. We’ve also explained how binary search works and why it can be an effective tool for optimizing your code.

By using binary search in your PHP applications, you can significantly improve the performance of array searches. Whether you choose to use the basic implementation or the recursive implementation, binary search is a powerful technique that every PHP developer should be familiar with.