PHP檢查數量比數組元素的值越小

Question

這似乎很簡單，但我想不出做最徹底的方法...

基本上我有一個排序的數組，像這樣的數字：

$array1 = [3, 7, 12, 63, 120, 512, 961]; 

我需要做的是檢查對一些數組中的每個元素可以是這樣的：

$number = 320; 

，我需要得到其在本例中的數字旁邊的元素它將是1 20因爲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循環在這裏用數組的長度檢查，但你很可能會看到它變得非常長，它肯定是不乾淨。如何做得更好？

Answer 1

因爲它是一個排序數組，所以你正在處理那麼我推薦你實現二進制搜索算法，它具有時間複雜度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

Answer 2

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