给定的数组有重复的元素，所以基本上，我想找到我搜索的元素的最后一次出现的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。有什么建议吗?
我没有看到你的循环，但我认为这真的很容易使用，以获得这样的功能
$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
首先，对于二进制搜索，你的数组必须排序，如果你的数组没有排序，你可以使用简单的方法，如
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 ;
}
并在上面定义$result while()以避免每次用-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;