CODEWITHSUNDEEP
phparrays
Mohammad Shahpari
Mohammad Shahpari

Reputation: 1

Binary search in array

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
}

Upvotes: 0

Views: 1668

Answers (2)

sumon cse-sust
sumon cse-sust

Reputation: 454

$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));

Upvotes: 1

Paolo
Paolo

Reputation: 15847

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;
}

Upvotes: 1

Related Questions