Binary Search in C++

Searching Element in an Array

Why is there a need for binary search in C++? Well, searching an element is one of the key operations performed on an array. Given a single dimensional array A with N elements, we want to search an element m (m<=N) from this array. One approach is to traverse through each array element and check if the element is present in the array and return its index if found. This is the Linear approach and called Linear search.  This approach is simple to apply and understand. However, time and space complexity constraints for large arrays make this approach less popular. Linear Search has the following disadvantages:

  1. For n elements in an array, if the element is at mth position, the number of search operations would be m. 
  2. Thus, for a large number of elements, Linear search is less efficient and takes more compilation time.

The binary search algorithm is an efficient alternative to a Linear search algorithm in terms of time complexity. Let us get a brief introduction to this popular search algorithm.

Binary Search:

Binary search is an effective searching algorithm to search for an element present in the given sorted array in O(log(n)) time. This follows the ‘divide and conquer’ algorithm as it repeatedly divides the given array into halves and compares the element to be searched with the middle element of the array. It follows the idea to search the element in the middle portion of the array.

Consider an example of searching a document from a column where the files have been arranged alphabetically. Let us assume that the document name starts with the alphabet ‘S’. We have two approaches to search for the document:

  1. To go through each file name and stop when we get the desired file. This is the linear approach of searching; However, this is time-consuming and exhausting as well.
  2. A smart approach would be to start looking from halfway since we already know that the files are arranged alphabetically, and S comes in the other half. Employing this approach repeatedly, the file could be searched more efficiently and consumes less time.

This approach is similar to the Binary Search algorithm.

Since we perform the search operation on the half interval of the given array with logarithmic time complexity, the Binary search algorithm is also known as half-interval search or logarithmic search

Algorithm: 

The binary Search algorithm employs the principle of divide and conquer. Its algorithm is as follows:

Let suppose, for any sorted array A (either sorted in ascending or descending), ‘e’ element has to be searched. Let ‘l’ be the lower limit index and ‘h’ be the higher limit index of array A.

Step 1: Start by finding the element in the middle position. Say, mid is the middle index and x be the middle element A[mid].

Step 2: If the element to be searched for is the same as the one found in the middle, return the index and exit from the loop.

Step 3: If element e is greater than x, i.e., e>x, we look for the element in the right subarray (if array sorted in ascending order) or look in the left subarray (if array sorted in descending order). 

If element e is less than x, i.e., e<x, we look for the element in the left subarray (if array sorted in ascending order) or in the right subarray (if array sorted in descending order).

For both cases, we need to update the value held by the lower or the upper bound of the array. 

  1. For the left subarray, ‘h’ is updated as h=mid-1. 
  2. and for the right subarray, l is updated as l=mid+1.

Step 4: Repeat steps 1 to step 3 on the new subarray thus obtained.

Given is the pictorial representation of binary search through an array of size 6 arranged in ascending order. We intend to search the element 78:

binary search algorithm

Based on the above algorithm, let us study another example:

Consider the given array arranged in ascending order with lower bound of index, l at 0 and higher bound of index, h at 6. Let us search the element 57 in the given array:

      31      39      44      52      56      57      66

Step 1: Find the element at the middle index, mid= l+h2, i.e. A[mid]. Here, it is 52 in this array.

      31      39      44      52      56      57      66

Step 2: Since 52 is not found in the middle, and 57>52, we search for it in the right subarray.

      31      39      44      52      56      57      66

Step 3:  We update the lower bound as, l=mid+1. In the right subarray, we find the middle element again repeating step 1. Here, it is 57.

If the element was supposed to be found in the left subarray, we would have updated the upper bound as h=mid-1.

Step 4: The element 57 is found at the mid.

      31      39      44      52      56      57      66

Step 4: Since we have found the element, return the index of the middle element and exit the loop.

If, the element is not found, the loop keeps running while l<=m.

Binary Search Function in C++

Iterative approach

Here, we make use of iterative statement while () to perform searching operation. The function definition for iterative approach is as follows:

//integer type array A arranged in ascending order
// x is element to search
int binary_search (int A [], int x) 
{  
int l=0, h=sizeof(A)-1;    //declaring upper and lower bound of array A
int mid = (l+h2);                           
while(l<=h)           
{
    if (x == A[mid])         // x is on right
        return mid;             // element found at middle index
    else if (x > A[mid])   
        l = mid + 1;           //updating lower bound
    else                           // x is left
        h = mid – 1;     
}
return -1;
}
//end of function definition

Recursive Approach

Binary search is performed by recursive approach i.e., calling the function recursively.

// A[] is an integer array sorted in ascending order 
int binary_search (int A [], int x, int l, h){
    if (l > h)
        return (-1);
    mid = l+b2;
     if (x == A [mid]);
            return mid;                 //element found at middle
        else if (x > A[mid])        // x is on right side
            return binary_search (A, x, mid + 1, h);    //recursive function call
        else                               // x is on left side
            return binary_search (A, x, l, mid - 1);
}
//end of function definition

Possible implementation Error

Binary search is often said to be difficult for implementing. However, if proper exiting conditions are employed, Binary search works efficiently. One should keep the following points in mind:

  1. The exit conditions of the loop must be specified correctly to avoid infinite iterations.
  2. The lower limit should never exceed the upper limit otherwise infinite iteration might crash the system.

Time Complexity

For Binary Search Algorithm, the best-case time complexity is given by O (1). This is when the central index element matches the given search element directly.

The average and worst case time complexity of this search algorithm is O (log(n)).

Let us assume that it took K iterations in binary search to search the desired element

As we have observed from the above given examples, the array/subarray divides itself into halves in each iteration. Let us assume that the length of the given array is n. Therefore, after performing K iterations, the length of the array would become n2k .

Also, we know that the array size would reduce to become 1 after performing K divisions over it.

Thus, we obtain the following relation:

n2k=1

Solving the given equation for n, we get the value of n as

n=2k

Put log on both sides we get 

n =2k

n =k×2

Solving for k, we get

k=n

Now the time complexity would be given by O(log(n)). Therefore, binary search runs in the logarithmic time in its worst-case scenario. This means that it would make O(log(n)) comparisons while implementation.

Space Complexity

Space complexity unlike time complexity depends on whether the iterative or the recursive approach has been implemented. Following factors govern space complexity in both approaches:

  1. Iterative approach controls iteration through looping statements and passes new values to the next iteration.
  2. Recursive approach implements boundary conditions and passes new values to next recursive function call. No looping statements are used in this approach.

Space Complexity (Iterative approach): 0(1)

Space complexity (Recursive approach): O (log (n))

In the word RAM model of computation, binary search takes O(1) space complexity. Here, the search algorithm requires three element pointers.

Advantages of Binary Search Algorithm

  1. Since it follows the technique to eliminate half of the array elements, it is more efficient as compared to linear search for large data.
  2. Better time complexity and thus takes less compilation time. 
  3. An improvement over linear search as it breaks the array down in half rather than sequentially traversing through the array elements.

Limitations of Binary Search Algorithm

  1. A binary search algorithm could only be implemented over a sorted array. 
  2. Small unsorted arrays would take considerate time in sorting and then searching the desired element. So, binary search is not preferred in such cases.
  3. It has a poor locality of reference compared to the linear search algorithm when comes to in-memory searching for short intervals.

Applications of Binary Search

  1. This algorithm is used to search element in a given sorted array with more efficiency.
  2. It could also be used for few other additional operations like- to find the smallest element in the array or to find the largest element in the array.

This brings us to the end of the blog on the concept of Binary Search in C++. We hope that you found this comprehensive and helpful and were able to gain the required knowledge. If you wish to up-skill and learn more such concepts, you can check out the pool of Free online courses on Great Learning Academy.

Also, if you are preparing for Interviews, check out these Interview Questions for C++ to ace it like a pro.

2

LEAVE A REPLY

Please enter your comment!
Please enter your name here

2 × 2 =