1. <?php
2.  
3. function linearSearch(array $haystack, $needle)
4. {
5.     $haystackSize = count($haystack);
6.    
7.     for ($i = 0; $i < $haystackSize; $i++) {
8.         if ($haystack[$i] == $needle) {
9.             return $i;
10.         }
11.     }
12.    
13.     return -1;
14. }
15.  
16. function linearSearchWithSentinel(array $haystack, $needle)
17. {
18.     $haystack[] = $needle;
19.    
20.     for ($i = 0; ; $i++) {
21.         if ($haystack[$i] == $needle) {
22.             return $i == count($haystack) ? -1 : $i;
23.         }
24.     }
25. }
26.  
27. function prepareHaystack(int $n)
28. {
29.     $haystack = [];
30.     for ($i = 0; $i < $n; $i++) {
31.         $haystack[] = random_int(1, $n * 10);
32.     }
33.    
34.     return $haystack;
35. }
36.  
37. $iterations = 1000;
38. $linearSearchTime = 0.0;
39. $linearSearchWithSentinelTime = 0.0;
40.  
41. for ($i = 0; $i < $iterations; $i++) {
42.     $n = random_int(1, 100000);
43.     $haystack = prepareHaystack($n);
44.     $needle = random_int(1, $n);
45.    
46.     $time_start = microtime(true);
47.     linearSearch($haystack, $needle);
48.     $linearSearchTime += (microtime(true) - $time_start);
49.    
50.     $time_start = microtime(true);
51.     linearSearchWithSentinel($haystack, $needle);
52.     $linearSearchWithSentinelTime += (microtime(true) - $time_start);
53. }
54.  
55. echo 'Linear search avg time : ' . round($linearSearchTime / $iterations, 6) . PHP_EOL;
56. echo 'Linear search with sentinel avg time : ' . round($linearSearchWithSentinelTime / $iterations, 6) . PHP_EOL;
57.  
58.