DEV Community

Ayowande Oluwatosin
Ayowande Oluwatosin

Posted on

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)

Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

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).

Sentry blog image

How I fixed 20 seconds of lag for every user in just 20 minutes.

Our AI agent was running 10-20 seconds slower than it should, impacting both our own developers and our early adopters. See how I used Sentry Profiling to fix it in record time.

Read more

Top comments (0)

nextjs tutorial video

Youtube Tutorial Series 📺

So you built a Next.js app, but you need a clear view of the entire operation flow to be able to identify performance bottlenecks before you launch. But how do you get started? Get the essentials on tracing for Next.js from @nikolovlazar in this video series 👀

Watch the Youtube series

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay