Find position of an element of array using binary search
Here is details of problem description.
/** write a function to search a value in an array and return index or position of array element,
* if not found return -1.
* for example, you have given an array like $array=[1,2,3,5,9,11,14,19];
* $search=11; find the position of 11 in the array.
* use binary search only.
*/
function binaySearch($array, $value)
{
// write your code from here
return 0;
}
$array = [1, 2, 3, 5, 9, 11, 14, 19];
$search = 11;
echo binaySearch($array, $search);
Here one important thing is that "Binary search can be implemented only on a sorted list of items". If the elements are not sorted already, we need to sort them first.
Here is the solution.
function binaySearch($array, $value)
{
// write your code from here
$position = -1;
//check the array is empty or not. If the array is empty then, return -1;
if (count($array) == 0) {
return $position;
}
$low = 0;// declare low as zero which is first index
$high = count($array) - 1;//declare high which is last index
while ($low <= $high) {
$mid = floor(($low + $high) / 2);//declare middle and assign average of $low and $high
if ($array[$mid] == $value) {
$position = $mid;//found the searching value
break;
} elseif ($array[$mid] > $value) {
$high = $mid - 1;//reassign high, may be the searching value is on left side from the middle.
} else {
$low = $mid + 1;////reassign low, may be the searching value is on right side from the middle.
}
}
return $position;
}
If you run this code then you will get 5 as output. change the searching value and run again to understand the logic.
If you found any issue contact with me (talemulwi@gmail.com).
Here is full source code link- https://github.com/talemul/Problem-Solving/blob/main/find-position-using-binary-search.php
Thank you.