快速的方式來搜索這個PHP陣列的關聯數組

Question

我有以下的PHP數組;

array(
    (int) 0 => array(
     'records' => array(
      'id' => '25', 
      'parent_id' => '1', 
      'address' => '896167', 
     ) 
    ), 
    (int) 1 => array(
     'records' => array(
      'id' => '26', 
      'parent_id' => '2', 
      'address' => '890812', 
     ) 
    ), 
    (int) 2 => array(
     'records' => array(
      'id' => '28', 
      'parent_id' => '16', 
      'address' => '8A3813', 
     ) 
    ), 
    (int) 3 => array(
     'records' => array(
      'id' => '29', 
      'parent_id' => '17', 
      'address' => '8A3914', 
     ) 
    ) 
) 

假設我想找到哪個鍵已經'id' => '29'，究竟是通過這個數組來搜索並返回正確的鍵的快捷方式？在這種情況下，正確的答案是3.

編輯：有人會建議是否使用foreach循環訪問數組或使用array_search會更快嗎？還是他們的速度相同？

Answer 1

foreach ($data as $key => $value) { 
    if ($value['records']['id'] == '29') break; 
} 
echo $key; 

以線性時間完成。

如果你的數組是按ID排序的，你可以做一個二進制搜索，而不是在對數時間內完成。

function binary_search($needle, $haystack) { 
    $min = 0; 
    $max = count($haystack); 
    while ($max >= $min) 
    { 
     $mid = (int) (($min + $max)/2); 
     if ($haystack[$mid]['records']['id'] == $needle) return $mid; 
     else if ($haystack[$mid]['records']['id'] < $needle) $min = $mid + 1; 
     else $max = $mid - 1; 
    } 
    // $needle was not found 
    return false; 
} 

echo binary_search('29', $data); 

Answer 2

您的數據結構上不能使用array_search()。您的foreach解決方案的時間複雜度爲O(n)（因此也會有array_search()）。

你說這些記錄是按照它的ID排序的。然後你可以做binary search，它的表現要比O(log(n))好得多。

Answer 3

您可以使用binairy搜索算法是這樣的：

$searchableArray = array(
        0 => array(
         'records' => array(
          'id' => '25', 
          'parent_id' => '1', 
          'address' => '896167', 
         ) 
        ), 
        1 => array(
         'records' => array(
          'id' => '26', 
          'parent_id' => '2', 
          'address' => '890812', 
         ) 
        ), 
        2 => array(
         'records' => array(
          'id' => '28', 
          'parent_id' => '16', 
          'address' => '8A3813', 
         ) 
        ), 
        3 => array(
         'records' => array(
          'id' => '29', 
          'parent_id' => '17', 
          'address' => '8A3914', 
         ) 
        ) 
       ); 

$foundKey = findKey($searchableArray, 29); 
echo "Found key: " . $foundKey; 

function findKey($searchableArray, $key){ 
    $splittedArray = splitArray($searchableArray); 
    if(isInLeftChunk($splittedArray[0], $key)){ 
     if(! isOnlyElement($splittedArray[0])){ 
      return findKey($splittedArray[0], $key); 
     } 
     return key($splittedArray[0]); 
    } 
    elseif(isInRightChunk($splittedArray[1], $key)){ 
     if(! isOnlyElement($splittedArray[1])){ 
      return findKey($splittedArray[1], $key); 
     } 
     return key($splittedArray[1]); 
    } 

    // Element not found 
    return false; 
} 

function isOnlyElement($arrayChunk){ 
    return count($arrayChunk) == 1; 
} 

function isInLeftChunk($arrayChunk, $key){ 
    end($arrayChunk); 
    $latestKey = key($arrayChunk); 
    if(is_int($latestKey)){ 
     return $arrayChunk[ $latestKey ]['records']['id'] >= $key; 
    } 
    return $arrayChunk[ $latestKey ]['id'] >= $key; 
} 

function isInRightChunk($arrayChunk, $key){ 
    reset($arrayChunk); 
    $firstKey = key($arrayChunk); 
    if(is_int($firstKey)){ 
     return $arrayChunk[$firstKey]['records']['id'] <= $key; 
    } 
    return $arrayChunk[ $firstKey ]['id'] <= $key; 
} 

function splitArray($unsplittedArray){ 
    $arrayLenght = count($unsplittedArray); 
    if($arrayLenght == 1){ 
     return array_chunk($unsplittedArray, $arrayLenght, true); 
    } 

    $odd = $arrayLenght % 2 != 0; 
    if($odd){ 
     $arrayLenght += 1; 
    } 
    $arrayLenght = $arrayLenght * 0.5; 

    return array_chunk($unsplittedArray, $arrayLenght, true); 
}