fork download
copy 
  1. <?php
  2.  
  3. //recursive variant
  4. function searchBin($arr, $lo, $hi, $search) {
  5.  
  6.          if($lo <= $hi) {
  7.  
  8.             $m = ($lo + $hi) >> 1;
  9.  
  10.             if($arr[ $m ] == $search) return($m);
  11.  
  12.             else if($arr[$m] > $search) {
  13.  
  14.                   return searchBin($arr, $lo, $m - 1, $search);
  15.             } else {
  16.  
  17.                   return searchBin($arr, $m + 1, $hi, $search);
  18.             }
  19.  
  20.          }
  21.          return -1;
  22. }
  23.  
  24.  
  25. //recursive variant
  26. function searchBin2($arr, $lo, $hi, $search) {
  27.  
  28.          if($lo > $hi) return -1;
  29.  
  30.             $m = ($lo + $hi) >> 1;
  31.  
  32.             if($arr[ $m ] == $search) return($m);
  33.  
  34.             else if($arr[$m] > $search) {
  35.  
  36.                   return searchBin($arr, $lo, $m - 1, $search);
  37.             } else {
  38.  
  39.                   return searchBin($arr, $m + 1, $hi, $search);
  40.             }
  41. }
  42.  
  43. //iterative solution
  44. function binSearch($arr, $lo, $hi, $search) {
  45.          $pos = -1;
  46.  
  47.          while($lo <= $hi) {
  48.  
  49.                $m = ($lo + $hi) >> 1;
  50.                if($arr[$m] == $search) {
  51.                   $pos = $m;
  52.                   break;
  53.                } else if($arr[$m] > $search) {
  54.                   $hi = $m - 1;
  55.                } else {
  56.                   $lo = $m + 1;
  57.                }
  58.          }
  59.          return $pos;
  60. }
  61.  
  62. $arr = array(-9,-3,-1,10,87,88,118,180,280,480,580,780);
  63.  
  64.  
  65. $n = sizeof($arr);
  66.  
  67. $search = 87;
  68.  
  69. $pos = binsearch($arr, 0, $n - 1, $search);
  70.  
  71. echo"Search: ". $search;
  72.  
  73. echo" Finding at position: ". $pos;
  74.  
  75. ?>
Success #stdin #stdout 0.02s 26336KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Search: 87 Finding at position: 4
https://ideone.com/BY1pPE
Binary Search - iterative and recursive
language:
PHP (php 7.3.5)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!