CODEWITHSUNDEEP
phpalgorithm
Jshee
Jshee

Reputation: 2686

Programming In General - Binary Search Algorithms

Given an array $array of N numbers and a key $key, write the binary search algorithm in plain English. If $array contains $key, return the index of the $key; otherwise, return -1.

Can someone show me how to do this?

Upvotes: 1

Views: 3463

Answers (3)

Saifullah khan
Saifullah khan

Reputation: 778

Here is a better non recursive solution.

function fast_in_array($elem, $array){
   $top = sizeof($array) -1;
   $bot = 0;

   while($top >= $bot)
   {
      $p = floor(($top + $bot) / 2);
      if ($array[$p] < $elem) $bot = $p + 1;
      elseif ($array[$p] > $elem) $top = $p - 1;
      else return TRUE;
   }

   return FALSE;
}

Upvotes: 0

neel.1708
neel.1708

Reputation: 315

I know this is little late :) ,but take it anyway.This also show that recursive function works faster than in_array()

 function binarySearch($A,$value,$starting,$ending)
    {
       if($ending<$starting)
       {
          return -1;
       }
       $mid=intVal(($starting+$ending)/2);

       if($value===$A[$mid])
          {
              return $mid;
          }
       else if($value<$A[$mid])
          {
             $ending=$mid-1;
          }
       else if($value>$A[$mid])
          {
             $starting=$mid+1;
          }

       return binarySearch($A,$value,$starting,$ending);
    }

    for($i;$i<1000000;$i++){
       $arr[$i]=$i;
    }
    $value =99999;

    $msc=microtime(true);
    $pos = in_array($value,$arr);
    $msc=microtime(true)-$msc; 

    echo "Time taken for in_array() : ".round($msc*1000,3).' ms <br>';
    if($pos>0)
    echo $value .' found.';
    else
    echo $value .' not found';

    echo "<br><br>";
    $msc=microtime(true);
    $pos = binarySearch($arr,$value ,0,1000000);
    $msc=microtime(true)-$msc; 

    echo "Time taken for recursive function : ".round($msc*1000,3).' ms<br>';
    if($pos>=0)
    echo $value .' found.';
    else
    echo $value .' not found';

Ouput:

Time taken for in_array() : 5.165 ms 
99999 found.

Time taken for recursive function : 0.121 ms
99999 found.

Upvotes: 1

jon_darkstar
jon_darkstar

Reputation: 16778

Doesn't seem like I should give you the code here, but maybe this description can help?

  1. Sort the list.

  2. Let i = length / 2

  3. Compare term at index i to your key.

    a. If they are equal, return the index.

    b. If key is greater than this term, repeat 3 (recurse) on upper half of list i = (i + length) / 2 (or (i + top) / 2 depending how you implement)

    c. If key is less than this term, repeat 3 on lower half i = i/2 or (i + bottom)/2

Stop recursion if/when the new i is the same as the old i. This means you've exhausted the search. Return -1

Be careful for off-by-one errors, which can make you exclude certain terms by mistake, or cause infinite recursion, but this is the general idea. Pretty straightforward.

Think of it as playing 'Guess the number' for the numbers 1 through 100. You take a guess, I tell you higher or lower. You say 50, I say lower. You say 25, I say higher. You say 37...

Upvotes: 7

Related Questions