Algorithms and The Different Types of Algorithms - Binary Search

feature-top

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

In today's article, we are going to continue our conversation in algorithms, specifically the 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 is 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 eliminate 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!!!

feature-top
feature-top
Hernando Cadet

Hi every one, I obtained a bachelor's degree in Bioinformatics back in 2006, from Claflin University, after I received my bachelor's degree, I gained full time employment as a software engineer at a Video Relay Service company, maintaining databases and developing software for a new developed device called the VPAD.

I worked at that company for two years, then I became a web developer, and worked for a magazine for three years. After that job, I worked as a Drupal web developer, as a subcontractor for the NIH, for a year and then left the job to go back to school.

Hernando Cadet Hi every one, I obtained a bachelor's degree in Bioinformatics back in 2006, from Claflin University, after I received my bachelor's degree, I gained full time employment as a software engineer at a Video Relay Service company, maintaining databases and developing software for a new developed device called the VPAD.

I worked at that company for two years, then I became a web developer, and worked for a magazine for three years. After that job, I worked as a Drupal web developer, as a subcontractor for the NIH, for a year and then left the job to go back to school.