使用二进制搜索查找数组中元素最后一次出现的索引 PHP

Question

给定的数组有重复的元素，所以基本上，我想找到我搜索过的元素最后一次出现的 index。

$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 ?

我不确定，为什么我会得到 -1。有什么建议吗？

Answer 1

我没有看到你的循环，但我认为使用它来获得这样的功能真的很简单

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

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

或者您可以简单地将 asort 函数与 array_search 一起使用，例如

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

Answer 2

并且还在 while() 之上定义 $result 以避免每次都被 -1 覆盖。因此你得到的结果是 -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;

Answer 3

首先，对于二进制搜索，你的数组必须排序，如果你的数组没有排序，你可以使用像

这样的简单方法

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

使用二进制搜索查找数组中元素最后一次出现的索引 PHP

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

php

arrays

binary-search