💡 مقایسه سرعت الگوریتم 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"