The World Of Algorithms – Binary Search

algorithms

Computer programming is very fascinating, as a computer scientist you must be able to solve very complex algorithmic problems. Understanding and mastering algorithms is part of the job of a computer scientist.

In today’s article we are going to continue our conversation in algorithms, specifically Binary Search Algorithm. When an item needs to be found in a sorted list of items, then the binary search algorithm, can be used to efficiently find that item.

The portion of the list that could contain the item is repeatedly divided, until all possible locations are narrowed to just one.

The binary search algorithm is also known as, half-interval search, binary chop, or logarithmic search. The idea behind this algorithm is to take advantage of the fact that, the array is sorted, by repeatedly dividing the search interval in half, to reduce the time complexity to O(Log n).

An algorithm is very complex, and in order to implement it, you’d have to understand all the details very well. Things such as the inputs and outputs to the problem must be known, also the initial values of variables and the variables should be defined.

The steps that should be taken in order to compute values, to arrive at the desired output should be thoroughly understood. Also a computer scientist should know if the steps are repeated, and he/she should know if a loop be useful in simplifying those repeated steps.

So for example, if I asked you to guess the number I am thinking about from 1 to 100 and every time, you say a number the I let you know that my number is higher or lower then the number you guessed, how would you guess that number using a programming language?

Well with a binary search you can guess the number by first guessing a numbers, figure out if the number is lower or higher, then you can narrow your search to the range of numbers you haven’t searched and discard the numbers to the left or right of the number you just guessed; depending on whether your target number is higher or lower than the number you guessed.

So for example, if you guessed 10 and I says is higher, then you know that the number would be between 11 and 100, then you guess a number between that range, if your guess was 45 and I say is lower than you’d eliminate any numbers that are higher than 45 and search between 11 and 44.

You would repeat the steps until you arrive at the number you are looking to find, in the list of sorted numbers.

Array_search is a PHP internal function, which is an example of a linear search, this means that is it very inefficient. Array_search is inefficient because it finds a match of an item in a data set, by iterating over the entire data set.

If the data set is small, and it is unordered it is okay to use a linear search algorithm, but for large data sets, the binary search algorithm is more efficient to find an item in a list of items, which are of course sorted.

The code below is an example of the binary search in PHP found online and on this website

<?php

function binarySearch(Array $arr, $x)

{

    // check for empty array

    if (count($arr) === 0) return false;

    $low = 0;

    $high = count($arr) - 1;

    while ($low <= $high) {

        // compute middle index

        $middle = floor(($low + $high) / 2);

        // element found at mid

        if($arr[$middle] == $x) {

            return true;

        }

        if ($x < $arr[$middle]) {

            // search the left side of the array

            $high = $middle -1;

        }

        else {

            // search the right side of the array

            $low = $middle + 1;

        }

    }

    // If we reach here element x doesnt exist

    return false;

}

// Driver code

$arr = array(1, 2, 3, 4, 5);

$value = 5;

if(binarySearch($arr, $value) == true) {

    echo $value." Exists";

}

else {

    echo $value." Doesnt Exist";

}

?>

Thank you for reading this article!!!