Last active
October 7, 2022 20:26
-
-
Save noweh/f44d12d831505409b9d3b8c8d84a65b2 to your computer and use it in GitHub Desktop.
Dichotomic search in PHP
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <?php | |
| // Create an array and hide a value in it | |
| $mySearchedValue = rand(0, 100); | |
| $array = array_merge( | |
| array_map(static function () { | |
| return rand(0, 100); | |
| }, array_fill(0, rand(9, 13), null)), | |
| [$mySearchedValue], | |
| array_map(static function () { | |
| return rand(0, 100); | |
| }, array_fill(0, rand(2, 4), null)) | |
| ); | |
| shuffle($array); | |
| // Remove duplicate values | |
| $array = array_unique($array); | |
| // Sort an array in ascending order | |
| sort($array); | |
| // Search $searchedValue in the array and return the index | |
| function dichotomicSearch($array, $searchedValue, $begin, $end) { | |
| if ($begin <= $end) { | |
| // Compute middle index | |
| $middle = ($begin+$end)>>1; // the same that: floor(($begin+$end)/2); | |
| if ($array[$middle] === $searchedValue) { // If the middle index has the value | |
| return $middle; | |
| } elseif ($array[$middle] < $searchedValue) { // If my value is higher, search the right side | |
| return dichotomicSearch($array, $searchedValue, $middle+1, $end); | |
| } elseif ($array[$middle] > $searchedValue) { // If my value is lower, search the left side | |
| return dichotomicSearch($array, $searchedValue, $begin, $middle-1); | |
| } | |
| } | |
| // My value is not in the array | |
| return -1; | |
| } | |
| var_dump('array', $array); | |
| echo 'searchedValue: ' . $mySearchedValue . "\r\n"; | |
| echo 'index found: ' . dichotomicSearch($array, $mySearchedValue, 0, count($array) - 1); | |
| ?> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment