English
English
The halving search algorithm in PHP, also known as binary search, is a classic method for efficiently locating an element’s position in an ordered array. It repeatedly divides the search range in half and compares the target element with the middle element, quickly narrowing down the search scope until the target is found or confirmed absent.
The core steps of binary search include:
Set the starting index of the array as left and the ending index as right.
Calculate the middle index mid as (left + right) / 2.
Compare the target value with the middle element: if equal, return the index mid indicating success.
If the target is less than the middle element, set right = mid - 1 to search the left half.
If the target is greater than the middle element, set left = mid + 1 to search the right half.
Repeat the steps until the target is found or left > right indicating failure.
Below is a PHP code example demonstrating the implementation of the binary search algorithm:
function binarySearch($arr, $target) {
$left = 0;
$right = count($arr) - 1;
while ($left <= $right) {
$mid = intval(($left + $right) / 2);
if ($arr[$mid] == $target) {
return $mid; // Position of target value
}
if ($arr[$mid] < $target) {
$left = $mid + 1; // Continue search in right half
} else {
$right = $mid - 1; // Continue search in left half
}
}
return -1; // Target value not found
}
<p>$arr = [1, 3, 5, 7, 9, 11, 15];<br>
$target = 7;<br>
$index = binarySearch($arr, $target);<br>
if ($index != -1) {<br>
echo "Target value $target is at position $index in the array";<br>
} else {<br>
echo "Target value $target does not exist in the array";<br>
}<br>
The above code defines a binarySearch function that takes an ordered array and a target value as input, returning the index of the target in the array or -1 if it does not exist.
The time complexity of binary search is O(log N), where N is the length of the array. Since each search step halves the search space, its efficiency is much higher than linear search.
This makes binary search ideal for quickly locating elements in large ordered arrays.
Binary search significantly narrows the search range and reduces comparison counts, enabling fast location especially in large datasets.
In applications with frequent search operations, using binary search greatly lowers time cost and enhances overall execution efficiency by avoiding unnecessary traversal.
This article systematically explained the principles and implementation of the PHP halving (binary) search algorithm, supported by code examples. The algorithm features low time complexity and high efficiency, suitable for fast searching in ordered arrays. Mastering it helps developers enhance their ability to solve search problems and improve program performance.
