CODEWITHSUNDEEP
phparraysbinary-search
Wild Widow
Wild Widow

Reputation: 2549

finding the index of last occurrence of an element in an array using binary search PHP

The array given has duplicate elements, So basically, I want to find the index of the last occurrence of the element I've searched. 

$arr = array(2, 3, 4, 4, 5, 6, 4, 8);
$x = 4; // number to search
$low = 0;
$high = count($arr)-1;
// I want this function to return 6 which is the index of the last occurrence of 4, but instead I'm getting -1 .
function binary_search_last_occ($arr, $x, $low, $high)
{
    while ($low <=$high)
    {
        $mid = floor(($low+$high)/2);
        $result = -1;
        if ($arr[$mid] == $x)
        {
            // we want to find last occurrence, so go for
            // elements on the right side of the mid 
            $result = $mid;
            $low = $mid+1;
        }
        else if($arr[$mid] > $x)
        {
            $high = $mid-1;
        }
        else
            $low = $mid+1;
    } 
    return $result;  
}
echo binary_search_last_occ($arr, $x, $low, $high); // outputs -1 ?

I'm not sure, why I'm getting -1. Any suggestions?

Upvotes: 3

Views: 1191

Answers (3)

Noor
Noor

Reputation: 99

First of all for binary search your array must be sorted, if your array is not sorted you can use simple method like

function binary_search_last_occ($arr, $x, $low, $high)
{
    $last_occ = -1;
    while ($low <=$high)
    {
         if($arr[$low] == $x)
            $last_occ = $low;
         $low++;
    }
    return $last_occ ;  
}

Upvotes: 2

jitendrapurohit
jitendrapurohit

Reputation: 9675

And also define $result above while() to avoid overriding every time with -1. Hence you get the result as -1.

$result = -1;

while ($low <=$high)
{
    $mid = floor(($low+$high)/2);

    if ($arr[$mid] == $x)
    {
        // we want to find last occurrence, so go for
        // elements on the right side of the mid 
        $result = $mid;
        $low = $mid+1;
    }
    else if($arr[$mid] > $x)
    {
        $high = $mid-1;
    }
    else
        $low = $mid+1;
} 
return $result;

Upvotes: 1

Narendrasingh Sisodia
Narendrasingh Sisodia

Reputation: 21422

I didn't seen your loop but I think this'll really simple to use to gain such functionality 

$arr = array(2, 3, 4, 4, 5, 6, 4, 8);
$result = [];
foreach($arr as $key => $val){
    $result[$val][] = $key;
}

echo end($result[4]);//6

Or you can simply use the asort function along with array_search like as

$arr = array(2, 3, 4, 4, 5, 6, 4, 8);
asort($arr);
echo array_search(4,$arr);//6

Upvotes: 2

Related Questions