In this article, we are covering most of the Binary Search based problem and respective optimum solutions.

Before we start let me explain Binary Search in detail.

Data structure and Algorithms Binary Search

Binary search is a fast search algorithm with run-time complexity of Ο(log n). This search algorithm works on the principle of divide and conquer. For this algorithm to work properly, the data collection should be in the sorted form.
The binary search looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of the item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the sub-array reduces to zero.

How Binary Search Works?

As depicted in below diagram,

For a binary search to work, it is mandatory for the target array to be sorted. We shall learn the process of binary search with a pictorial example. The following is our sorted array and let us assume that we need to search the location of value 14 using binary search.
First, we shall determine half of the array by using this formula,
int mid = (begin + end) / 2;

Then check if A[mid] is expected k, else check if it is less than 14, set the begin as mid+1 as per below logic,
if(A[mid]==k)
{
   return mid;
}
else if(A[mid]>k)
{
   end = mid - 1;
}
else
{
   begin = mid + 1;
}
 
Then it will go for next iteration and recalculate the mid, and check for A[mid] ==k, now it is matching and we have resolved the problem.

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) / 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

Problems and Solutions

Here are few important examples of Binary Search based Algorithm problems:

Problem 1.1: Computing Square Root 

Click here to download - Implement a fast Square root of an integer function

Problem 1.2: Search A sorted Array For k

Click here to download - Implement a fast Search A sorted Array For k function

Problem 1.3: Search A sorted Array For first greater than k occurrence

Click here to download - Implement a fast Search A sorted Array For first greater than k occurrence function