Write a program to implement binary search in PHP.
Given a sorted array, write a PHP code to search an element using binary search algorithm.
For example –
Input : { 1, 3, 5, 6, 7, 8, 9} , k = 6
Output: 3 (6 is found at 3rd index)
Before writing php code, let’s understand what is binary search.
Binary Search
In binary search, first we compute mid by using start and end index. In next step, we compare the value present at mid index to the value k. If search value is found, then the index of the middle element is returned else the algorithm repeats if the value is less than or greater than the middle element.
If the search value is less than or greater than the middle element, than the search continues in the lower or upper half of the array.
The time complexity of binary search is O(logn).
Important points regarding binary search
i) Binary search works only with sorted array.
ii) The time complexity of a binary search is O(logn).
How to reverse a number in PHP
Binary Search in PHP – Code
We have discussed the binary search and it’s algorithm. Let’s write a php code to search an element in an array using binary search.
In this example, I have created one binarySearch method which accepts array and element to be searched in an array. The function return index if the value is found else it 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; } |
Binary search iterative and recursive algorithm video tutorial
