Binary search in PHP

What is binary search?

Binary search is a search algorithm used to efficiently find the position of a target value in a sorted array (or list). It works by repeatedly splitting the search range in half and comparing the middle element to the target value.

The binary search algorithm follows the following steps:

• Start with the entire sorted array.

• Set the left pointer to the first element of the array and the right pointer to the last element.

• Calculate the middle index as the average of the left and right pointers (integer division).

• Compare the value at the intermediate index to the target value.

• If the intermediate value is equal to the target value, the search is successful and the algorithm returns the index.

• If the target value is greater than the middle value, eliminate the left half of the search range by updating the left pointer to mid 1.

• If the target value is less than the middle value, eliminate the right half of the search range by updating the right pointer to mid - 1.

• Repeat steps 3 to 7 until the target value is found or the search range is empty (the left pointer is larger than the right pointer).

• If the search range is empty and the target value is not found, the algorithm concludes that the target value does not exist in the array and returns -1 or an appropriate indication.

Binary search is a very efficient algorithm with a time complexity of O(log n), where n is the number of elements in the array. It is particularly effective for large sorted arrays because it quickly narrows the search range by splitting it in half at each step, allowing for fast searches even with a large number of elements.

Binary search PHP program

Method 1 - Using iteration

Example

<?php
function binarySearch($arr, $target) {
   $left = 0;
   $right = count($arr) - 1;
   while ($left <= $right) {
      $mid = floor(($left + $right) / 2);
      // Check if the target value is found at the middle index
      if ($arr[$mid] === $target) {
         return $mid;
      }
      // If the target is greater, ignore the left half
      if ($arr[$mid] < $target) {
         $left = $mid + 1;
      }
      // If the target is smaller, ignore the right half
      else {
         $right = $mid - 1;
      }
   }
   // Target value not found in the array
   return -1;
}
// Example usage 1
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 91;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.<br>";
} else {
   echo "Target value found at index $resultIndex.<br>";
}
// Example usage 2
$targetValue = 42;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.";
} else {
   echo "Target value found at index $resultIndex.";
}
?>

Output

Target value found at index 9.
Target value not found in the array.

Method 2 - Using Recursion

Example

<?php
function binarySearchRecursive($arr, $target, $left, $right) {
   if ($left > $right) {
      // Target value not found in the array
      return -1;
   }
   $mid = floor(($left + $right) / 2);
   // Check if the target value is found at the middle index
   if ($arr[$mid] === $target) {
      return $mid;
   }
   // If the target is greater, search the right half
   if ($arr[$mid] < $target) {
      return binarySearchRecursive($arr, $target, $mid + 1, $right);
   }
   // If the target is smaller, search the left half
   return binarySearchRecursive($arr, $target, $left, $mid - 1);
}
// Wrapper function for the recursive binary search
function binarySearch($arr, $target) {
   $left = 0;
   $right = count($arr) - 1;
   return binarySearchRecursive($arr, $target, $left, $right);
}
// Example usage
$sortedArray = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
$targetValue = 16;
$resultIndex = binarySearch($sortedArray, $targetValue);
if ($resultIndex === -1) {
   echo "Target value not found in the array.";
} else {
   echo "Target value found at index $resultIndex.";
}
?>

Output

Target value found at index 4.

in conclusion

In summary, binary search is a powerful algorithm that can efficiently find a target value in a sorted array. It provides two common implementations: iterative and recursive. The iterative method uses a while loop to repeatedly split the search range in half until the target value is found or the range becomes empty. It has a simple implementation and is perfect for most scenarios. On the other hand, recursive methods employ recursive functions to perform binary searches. It follows the same logic as the iterative method, but uses function calls instead of loops. Recursive binary search provides a cleaner implementation, but may have a slightly higher overhead due to function call stack manipulation. Overall, both methods provide an efficient and reliable way to perform binary search operations.

The above is the detailed content of Binary search in PHP. For more information, please follow other related articles on the PHP Chinese website!