Bacana, acho que eu nunca tinha ouvido falar do assunto. Daí me interessei e fiz um script em PHP pra realizar essa busca.
Sei que não é a resposta procurada pelo autor, mas estou compartilhando para futuros "pesquisadores".
Segue o código:
$lista = Array(12,13,15,19,24,28,39,57,59,63,67,69,74);
$el = 69; // Elemento a ser encontrado
$id = 0;
while (is_array($lista)){
$ini = 0; // Elemento inicial da lista
$mid = floor(count($lista)/2); // Elemento no meio da lista
$end = count($lista)-1; // Elemento final da lista
echo 'INI: '.$lista[$ini].' | ID: '.$ini.PHP_EOL;
echo 'MID: '.$lista[$mid].' | ID: '.$mid.PHP_EOL;
echo 'END: '.$lista[$end].' | ID: '.$end.PHP_EOL;
echo '---------------------------------'.PHP_EOL;
if ($lista[$mid] < $el){ // Se o elemento estiver na segunda parte da lista
$tmp = Array();
for($i = $mid; $i <= $end; $i++)
$tmp[] = $lista[$i];
$id += $mid;
$lista = $tmp;
} elseif ($lista[$mid] > $el) { // Se o elemento estiver na primeira parte da
// lista
$tmp = Array();
for($i = $ini; $i < $mid; $i++)
$tmp[] = $lista[$i];
$lista = $tmp;
} else { // Elemento no meio da lista
$id += $mid;
$lista = PHP_EOL.'Encontrado: '.$lista[$mid].' | ID: '.$id;
}
// Checou todos os itens e não encontrou.
if ($ini == $end && is_array($lista) ) $lista = 'O Item nao existe!';
}
echo $lista;
Saída:
INI: 12 | ID: 0
MID: 39 | ID: 6
END: 74 | ID: 12
---------------------------------
INI: 39 | ID: 0
MID: 63 | ID: 3
END: 74 | ID: 6
---------------------------------
INI: 63 | ID: 0
MID: 69 | ID: 2
END: 74 | ID: 3
---------------------------------
Encontrado: 69 | ID: 11