PHP Program to implement binary search algorithm in an array

Before going to the program let's have a look at the binary search algorithm

What is a Binary search algorithm?

Search algorithms are used to find the occurrence of an element in a list of elements. It checks for a match in the list and returns the index value where it got the match, otherwise gives a message that the element is not found in the list.

The binary search algorithm is also called the "half interval algorithm" or "logarithmic algorithm". It works on an ordered list, which means it searches the element in a sorted array. If the given array is not sorted, the elements need to be sorted first and then the search will be implemented on it. This algorithm works on a divide and conquers method. It will first divide the list into two by taking the middle element of the list and checking whether the search element matches with the middle element. If both are equal then returns the index otherwise, the algorithm chooses any one of the sublists where the chance is more the search element to be present. This division and search of sublists will continue until the size of the sublist reduces to zero.

It works faster on large lists than the smaller ones. The binary search tree and B-tree data structures are based on binary search. The worst-case time complexity of Binary search is O(logn).

How to implement binary search in PHP?

• A function could be written to implement binary search in PHP. The sorted array and search item can be passed as input variables to the function. and,
• Using a while loop the middle element is computed first then checks the middle element with the search item if they are matched return true,
• Now rebound the list to check by comparing their values, if search element < middle element reset the right boundary to the index just before middle element otherwise reset the left boundary to the index just after middle element.
• Repeat the above process until the size of sub-arrays reduces to zero.
• If the element doesn't exists then return false as the last statement in the function
• In the main section call the function with a sorted array, search value, and echo the results according to the return value from the function

Now, let's see the working of the Binary Search Algorithm. Take an array (6,7,8,9,11,14,18,23) and search element 18. We have 6 at the start,23 at last, and 11 at the middle, check if the middle one is 18. It's not, also 11 is smaller to 18 so now the list to search becomes (14,18,23) i.e., the right subarray. Here we will get a match with the middle element thus our search became successful.

ALGORITHM

STEP 1: Write a function binarySearch with variables array arr and search value item.

STEP 2: Initialise variables low 0 and high last index

STEP 3: Start a while loop to repeat until the condition low<=high,

STEP 4: Find the middle index of the array mid and check the middle element with the item if matches return true

STEP 5: Check if item<arr[mid] then last index becomes high=mid-1 else start index becomes low=mid+1

STEP 6: Now end the function by return false means no match found

STEP 7: Initialise an array arr with values and item to be searched

STEP 8: Call the binarySearch() with values arr, item and check the return value and echo the suitable result

                                          <?php

function binarySearch(Array $arr, $item)
{
 // check for empty array
 if (count($arr) == 0) return false;
 $low = 0;
 $high = count($arr) - 1;
 
 while ($low <= $high) {
  
  // compute middle index
  $mid = floor(($low + $high) / 2);

  // element found at mid
  if($arr[$mid] == $item) {
   return true;
  }

  if ($item < $arr[$mid]) {
   // search the left side of the array
   $high = $mid -1;
  }
  else {
   // search the right side of the array
   $low = $mid + 1;
  }
 }
 
 // If we reach here element x doesn't exist
 return false;
}

$arr = array(6,7,8,9,11,14,18,23);
$item = 18;
if(binarySearch($arr, $item) == true) {
 $index=array_search($item, $arr);
 echo " Element is present at index ".$index;
}
else {
 echo " Element is not present in the array";
}
?>
                                      

Element is present at index 6