这看起来很简单,但我无法弄清楚最干净的方法......
基本上我有一个排序数组,其数字如下:
$array1 = [3, 7, 12, 63, 120, 512, 961];
我需要做的是检查数组的每个元素与一个数字,如下所示:
$number = 320;
而且我需要得到这个例子中数字旁边的元素,它将是120,因为120 < $number < 512
。
嗯,我的方式有点工作是相当混乱我想:
foreach ($i = 0; $i < count($array1); $i++) {
if ($array[$i] < $number) {
// echo "do nothing, elements are smaller than number
} else {
if ($flag == true) {
// echo "elements are not smaller anymore and flag is set"
$getValue = $array[$i-1]; // last element which was smaller
$flag == false;
}
}
}
另一个问题是,如果$number
小于数组的最小元素或者大于数组的最大元素,我需要覆盖这些情况。对于这种情况,我创建另一个变量$t
并在每次迭代中检查它与数组的长度
$t = 0;
$len = count($array1);
// if element bigger than number and first iteration
if ($array[$i] > $number && $t == 0) {
}
$t += 1;
我把foreach循环留在了这里,但你可能会看到它变得非常长而且肯定不干净。怎么能做得更好?
由于它是您正在使用的排序数组,因此我建议您实现二进制搜索算法,该算法在时间复杂度上具有O(log(n))。
int binary_search(int A[], int key, int imin, int imax)
{
// continue searching while [imin,imax] is not empty
while (imin <= imax)
{
// calculate the midpoint for roughly equal partition
int imid = midpoint(imin, imax);
if(A[imid] == key)
// key found at index imid
return imid;
// determine which subarray to search
else if (A[imid] < key)
// change min index to search upper subarray
imin = imid + 1;
else
// change max index to search lower subarray
imax = imid - 1;
}
// key was not found
return KEY_NOT_FOUND;
}
来源:wikipedia.org
$array = [3, 7, 12, 63, 120, 512, 961];
$min = 0;
$max = count($array)-1;
$no = 320;
while ($min < $max)
{
$mid = (int)(($min+$max)/2);
if ($array[$mid] == $no) {
print $array[$mid-1]."<".$no."<".$array[$mid+1];
return;
}
else if($array[$mid] < $no) {
$min = $mid+1;
} else {
$max = $mid-1;
}
if($min == $max ) {
if($array[$min] > $no) {
print $array[$min-1]."<".$no."<".$array[$min];
return;
} else {
print $array[$min]."<".$no."<".$array[$min+1];
return;
}
}
}