Binary Search

Binary search is a quick search algorithm with an O run-time complexity (log n). This search algorithm operates on the divide and conquers principle. The data collection should be sorted for this algorithm to perform properly.

Binary search looks for a certain item by comparing the collection’s middlemost item. If a match is found, the item’s index is returned. If the item is greater than the middle item, the item is looked for in the sub-array to the left of the middle item. Otherwise, the item is sought in the sub-array to the right of the center item. This method is repeated on the sub-array until the size of the sub-array is reduced to zero.

Pseudocode

The pseudocode of binary search algorithms should look like this −

Procedure binary_search
   A ← sorted array
   n ← size of array
   x ← value to be searched

   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.
   
      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
      
      if A[midPoint] < x
         set lowerBound = midPoint + 1
         
      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint
   end while
   
end procedure