Write a program to implement binary search in PHP. Given a sorted array, we have to write a PHP code to search an element using binary search algorithm.
Important points regarding binary search
i) Binary search works with only sorted array.
ii) The time complexity of a binary search is O(logn).
iii) In binary search, we first calculate the mid value. After that we compare value needs to search to the middle element of an array. If a value matches with the middle element of an array then it’s index is returned otherwise the algorithm repeats if the value is less than or greater than the middle element.
How to reverse a number in PHP
Binary Search in PHP
Binary Search in PHP – Code
We have created one binarySearch method which accept array and value to be searched in an array. If value is found in an array then it’s index is return otherwise we return -1.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | <?php /** * Binary search implementation * * @param array $arr The sorted array * @param int $value The value needs to be search in an array * @return int The index of the search key if found, otherwise -1 */ function binarySearch($arr, $value) { $low = 0; $high = count($arr) - 1; while ($low <= $high) { //calculate mid $mid = ($low + $high)/2; /* If value we are searching found at mid position then return it's index */ if ($value == $arr[$mid]) { return $mid; } else if ($value < $arr[$mid]) { $high = $mid - 1; } else if ($value > $arr[$mid+1]) { $low = $mid + 1; } } return -1; } $arr = array(1, 3, 5, 6, 7, 8, 9); $value = 6; /* Call binary search function, which returns index at which value is found. */ $index = binarySearch($arr, $value); //if index is -1, then value is not present if ($index == -1){ echo "search key is not found"; } else { echo "search element is found at index ".$index; } |
