یوشا

💡 مقایسه سرعت الگوریتم binary search مقابل الگوریتم linear search برای آرایه های مرتب شده(sorted)

(برای آرایه های عددی سنگین)

$needle = range(1, 500000);

❌ Linear search algorithm

function search(array $numbers, $needle)
{
   $_totalItems = count($numbers);

   for ($i = 0; $i < $_totalItems; $i ++)
   {
      if ($numbers[$i] === $needle)
      {
         return TRUE;
      }
   }

   return FALSE;
}

📊 نتیجه(ms)
0.031199932098389
0.031199932098389
0.031199932098389
0.031199932098389
0.031199932098389
0.031199932098389
0.031200170516968
0.031200170516968
0.046799898147583
0.046800851821899

✅ Binary search algorithm

function search(array $numbers, $needle)
{
   $_low = 0;
   $_high = count($numbers) - 1;

   while ($_low <= $_high)
   {
      $_middle = (int) (($_low + $_high) / 2);
      if ($numbers[$_middle] > $needle)
      {
         $_high = $_middle - 1;
      }
      else if ($numbers[$_middle] < $needle)
      {
         $_low = $_middle + 1;
      }
      else
      {
         return TRUE;
      }
   }

   return FALSE;
}

📊 نتیجه(ms)
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0

x64 Hardware
32bit OS
PHP 5.6 CLI

کد از کتاب "PHP 7 Data Structures and Algorithms"