php - ¿Qué está mal con mi código? La matriz ordenada circularmente no muestra ningún resultado.

arrays sorted

Question

Hoy tuve una entrevista y la persona me hizo esta pregunta:

¿Cómo encontrar fácilmente un elemento en una matriz ordenada circularmente?

Como no sabía la respuesta, intenté encontrar una solución. Esto es lo que tengo:

Gracias

<?php
function searchincircularsorterlist($a, $len, $num) {
$start=0;
$end=$len-1;
$mid = 0;
while($start<$end) {
$mid=$start+$end/2;
if ($num == $a[$mid]) {
return $num;
}
if($num<$a[$mid]) {
if($num<$a[$start] && $a[$start]<=$a[$start+1])
$start=$mid++;
else
$end=$mid--;
}
else {
if($num>$a[$end] && $a[$end-1]<=$a[end])
$end=$mid--;
else
$start=$mid++;
}
}
if ($start == $end && $num == $a[$start]) {
return $num;
}
return -1;
}
$array = array(7,8,9,0,1,2,3,4,5,6);
var_dump(searchincircularsorterlist($array,sizeof($array),4));

Estoy tratando de trabajar con una matriz ordenada circularmente pero por alguna razón no funciona. ¿Qué pasa con mi código?

Answer 1

1) Aprender la prioridad de las operaciones . Debería tener: $ mid = ($ start + $ end) / 2; que terminó dividiendo $ end por 2 y luego $ start - el resultado. Por eso tienes un bucle infinito.

2) uso: $start=$mid+1; y no $start=$mid++; Eso ayudará a reducir el número de bucles.

<?php
function searchincircularsorterlist($a, $len, $num) {
$start=0;
$end=$len-1;
$mid = 0;
while($start<$end) {
$mid=($start+$end)/2;
if ($num == $a[$mid]) {
return $num;
}
if($num<$a[$mid]) {
if($num<$a[$start] && $a[$start]<=$a[$start+1])
$start=$mid+1;
else
$end=$mid-1;
}
else {
if($num>$a[$end] && $a[$end-1]<=$a[end])
$end=$mid-1;
else
$start=$mid+1;
}
}
if ($start == $end && $num == $a[$start]) {
return $num;
}
return -1;
}
$array = array(7,8,9,0,1,2,3,4,5,6);
var_dump(searchincircularsorterlist($array,sizeof($array),4));