我今天去面试,面试官问了我这个问题:
如何在循环排序的数组中轻松找到一个项目
因为我不知道答案,所以我试图找到解决办法。这是我拥有的:
谢谢
<?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));
我正在尝试使用循环排序的数组,但由于某种原因它不起作用。我的代码有什么问题?
最佳答案
1)学习priority of operations .你应该有: $mid=($start+$end)/2;你最终将 $end 除以 2 然后 $start - 结果。这就是你得到无限循环的原因。
2) 使用:$start=$mid+1;
而不是 $start=$mid++;
这将有助于减少循环次数
<?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));
关于php - 我的代码有什么问题 - 循环排序的数组不显示任何结果,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7975018/