поиск индекса последнего вхождения элемента в массив с использованием бинарного поиска Stack Overflow

Question

поиск индекса последнего вхождения элемента в массив с использованием бинарного поиска Stack Overflow

В данном массиве есть повторяющиеся элементы, поэтому в основном я хочу найти 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. Какие-либо предложения?

3

arrays binary-search php

Решение

Другие решения

Прежде всего для бинарного поиска ваш массив должен быть отсортирован, если ваш массив не отсортирован, вы можете использовать простой метод, как

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

2

А также определить $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;

1

Источник

Accepted Answer

Я не видел ваш цикл, но я думаю, что это будет действительно просто использовать для получения такой функциональности

$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

2