Search Algorithms

Understanding Binary Search in PHP

Binary search is a more efficient algorithm for finding an element in a sorted array. It works by repeatedly dividing the search interval in half. Here's a detailed breakdown of your binarySearch function:

function binarySearch(array $arr, float|int $x)
{
    $low = 0;
    $high = count($arr)-1;
    // $midIndex = (int) ($low + ($high - $low)/2);
    $i = 0;
    while($low <= $high){
        $i++;
        $midIndex = (int) ($low + (($high - $low)/2)); //the same as  intdiv($low + $high, 2);

        if($arr[$midIndex] == $x){
            return "The number {$x} was found in index {$midIndex} of the array. The number of iteration was {$i}";
        }elseif($x > $arr[$midIndex]){
            $low = $midIndex +1;
            echo $low."\n";
        }else{
            $high = $midIndex - 1;
        }
    }

return "The number {$x} was not found in the array";


}

echo binarySearch([1,2,3,4,5,6,7,8,9,10,44,45,46,47,48,49,50], 45)

The function binarySearch accepts two parameters:

1. $arr: A sorted array of integers.
2. $x: The number to be searched, which can be a float or an integer.
3. $low is initialized to the first index of the array.
4. $high is initialized to the last index of the array.
5. $i is a counter to keep track of the number of iterations.
6. The while loop runs as long as the search interval is valid ($low is less than or equal to $high).
7. $midIndex is calculated as the middle index of the current interval.
8. If the middle element is equal to $x, the function returns the index and the number of iterations.
9. If $x is greater than the middle element, adjust $low to midIndex + 1 (narrow the search to the upper half).
10. If $x is less than the middle element, adjust $high to midIndex - 1 (narrow the search to the lower half).

Understanding Linear Search in PHP

Linear search is one of the simplest searching algorithms used to find a particular element in an array. Let's break down the linearSearch function in PHP.

function linearSearch(array $arr, float|int $x)
{
    for($i=0; $i < count($arr); $i++){
        if($x === $arr[$i]){
            return "The number {$x} was found in index {$i} of the array\n";
        }
    }

    return "The number {$x} was not found in the array\n";
}

echo linearSearch([1,5,6,3,4,11,3,2], 4);

The function linearSearch accepts two parameters:

1. $arr: An array of integers.
2. $x: The number to be searched, which can be a float or an integer.
3. The for loop iterates over each element of the array. The count($arr) function returns the number of elements in the array.
4. Inside the loop, the code checks if the current element ($arr[$i]) is equal to $x. If a match is found, it returns a message indicating the index at which the number was found.
5. If the loop completes without finding the number, the function returns a message indicating that the number was not found in the array.
6. Linear search is straightforward and easy to implement. It sequentially checks each element of the array until the desired element is found or the end of the array is reached. This approach is simple but can be inefficient for large arrays, as it has a time complexity of O(n).

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