Binary search in array

Question

I wrote this code for a binary search but it has some problems. Can someone help me write better code?

function bs ($a,$val,$low,$high){
    if ($high < $low){
        return print "not found";
    }
    $mid= $low + (($high-$low)/2);
    if ($a[$mid]>$val){
        return bs ($a,$val,$low,$mid--);
    }else if  ($a[$mid]<$val){
        return bs ($a,$val,$low,$mid++);
    }else{
        return print 'found';
    }
}
$array=array(1,2,3,4,5,6,7);
bs ($array,5,0,6);

Problem

Fatal error: Allowed memory size of 1073741824 bytes exhausted (tried to allocate 65488 bytes) in D:\xampp\htdocs\bin2.php on line 15

BinarySearch(A[0..N-1], value, low, high) {
    if (high < low)
        return -1 // not found
    mid = low + ((high - low) / 2)  // Note: not (low + high) / 2 !!
    if (A[mid] > value)
        return BinarySearch(A, value, low, mid-1)
    else if (A[mid] < value)
        return BinarySearch(A, value, mid+1, high)
    else
        return mid // found
}

but have some problem -- How are we supposed to know what the problem is if you don't tell us? What doesn't work? What are the expected results and what did you get instead? — Amal
– Amal, Commented Nov 19, 2013 at 20:02
Fatal error: Allowed memory size of 1073741824 bytes exhausted (tried to allocate 65488 bytes) in D:\xampp\htdocs\bin2.php on line 15 — Mohammad Shahpari
– Mohammad Shahpari, Commented Nov 19, 2013 at 20:03
Looks like you might have an infinite loop with that recursive function. — webnoob
– webnoob, Commented Nov 19, 2013 at 20:04
You're not accounting for un-even divisions. $mid might come out to something like 2.5, then becomes 2.25, 2.125 etc... and you never ever stop recursing. — Marc B
– Marc B, Commented Nov 19, 2013 at 20:08

timiTao · Accepted Answer · 2018-03-13 14:08:21Z

The problem is that you have to cast

(($high-$low)/2)

to integer with

intval(($high-$low)/2)

Also calling

bs ($a,$val,$low,$mid--);
bs ($a,$val,$low,$mid++);

will decrement / increment $mid after the function call, so you should use

bs ($a,$val,$low,$mid-1);
bs ($a,$val,$low,$mid+1);

Also, the PHP code doesn't match with the pseudocode you posted below when you write

return bs ($a,$val,$low,$mid+1);

Should be instead

return bs ($a,$val,$mid+1,$high);

Finally I don't think

return print 'found';
return print 'not found';

will give the expected behaviour:

return -1;
return $mid;

So the whole thing became

function bs ($a,$val,$low,$high){
    if ($high < $low){
        return -1;
    }
    $mid= $low + intval(($high-$low)/2);
    if ($a[$mid]>$val){
        return bs ($a,$val,$low,$mid-1);
    }else if  ($a[$mid]<$val){
        return bs ($a,$val,$mid+1,$high);
    }else{
        return $mid;
    }
}

$array=array(1,2,3,4,5,6,7);
$idx = bs ($array,5,0,6); 

if($idx==-1)
{
    echo 'not found';
}
else
{
    echo 'Found at index' . $idx;
}

sumon cse-sust · Accepted Answer · 2019-06-11 16:53:45Z

1

$data_set = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21];
$search_item = 19;

function binary_search($search_item,$data_set){
    $start = 0;
    $end = count($data_set) - 1;
    while($start <= $end ){
        $mid = floor(($start + $end) / 2);
        if($search_item < $data_set[$mid]){
            $end = $mid - 1;
        }elseif($search_item > $data_set[$mid]){
            $start = $mid + 1;
        }elseif($search_item == $data_set[$mid]){
            return 'index=='.$mid.' and value=='.$search_item;
        }
    }
    return -1;
}

var_dump(binary_search($search_item,$data_set));

edited Jun 11, 2019 at 16:53

answered Mar 13, 2018 at 13:42

sumon cse-sust

4544 silver badges8 bronze badges

Collectives™ on Stack Overflow

Binary search in array

Problem

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Problem

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related