Binary Search

In this tutorial, you will learn how binary search works. Also, you will learn how to write the program using the binary search algorithm. In this blog post, you will find working examples of Binary Search in C, and C++.

Before implementing the code let’s first understand the binary search algorithm.

Binary search is a search algorithm. It is also known as half-interval search, logarithmic search, or binary chop. It is used to find the position of a target value within a sorted array.

Before implementing the binary search you need to remember that it can be implemented only on a sorted list of items. If the elements are not sorted already, we need to sort them first. See the below array,

int arr1[] = { 1, 2, 3, 4, 5}; //Binary Search can implement

int arr2[] = {5, 2, 0, 4};//Binary Search can not implement, we need to sort first

 

How Does Binary Search Work?

It begins by comparing an element in the middle of the array with the target element (an element that you want to find in the array). If the target element is equal to the middle element, its position in the array is returned.

But If the target element is not equal to the middle element, it checks whether the target element is lie in the lower half of the array or the upper half of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration.

Let’s see the steps and pseudo code for the iterative procedure. It will help you in understanding the binary search algorithm.

Suppose arr is a given integer array of n elements. These elements are arr0 , arr1 , arr2 , … arrn-1 ,arrn. Assume that the element of the array is already sorted in increasing order which means arr0 is the lowest element and arrn is the largest element of the array.

Now suppose T is a target value that you want to find in a given sorted array with binary search. So you need to follow the below steps:

1. Set start to 0 and end to (n-1).

2.If start>end, the search terminates as unsuccessful.

3. Set m to (start+end)/2 (the position of the middle element).

4.If (arrm < T), set start = m+1 and go to step 2.

5.If (arrm > T), set end = m-1 and go to step 2.

6. Now if (arrm ==T),  the search is done; return m.

 

The procedure may be expressed in pseudocode as follows:

function binary_search(arr, n, T) is
    start := 0
    end := n − 1
  flag := unsuccessful
    while (start ≤ end)  && (flag == unsuccessful)
        m := ((start + end) / 2)
        if arr[m] < T then
            start := m + 1
        else if arr[m] > T then
            end := m − 1
        else: 
            flag = m
    return flag

 

Examples of Implementing a Binary Search using C (Iteration Method):

#include<stdio.h>

int binarySearch(int *arr, int sizeofArray, int T)
{
    int index = -1;
    int start = 0;
    int end = (sizeofArray -1); //index of last element
    int med = 0;

    while((start <= end) && (index == -1))
    {
        //find the med of the array
        med = (start+end)/2;

        if(arr[med] < T)
        {
            //update start index with new value
            start = (med+1);
        }
        else if(arr[med] > T)
        {
            //update end index with new value
            end = (med-1);
        }
        else
        {
            index = med;
        }
    }

    return index;
}



int main()
{
    //sorted array
    int a[] = {1,2,3,4};

    //Calculate the array size
    const int sizeofArray = sizeof(a)/sizeof(int);

    //value which want to search
    const int value = 3;

    //Search value in given sorted array
    const int elementIndex =  binarySearch(a, sizeofArray, value);

    if(elementIndex == -1)
    {
        printf(" Element not found\n");
    }
    else
    {
        printf("%d", elementIndex);
    }

    return 0;
}

 

Binary Search Complexity:

Time Complexities:

  • Best case complexity: O(1)
  • Average case complexity: O(log n)
  • Worst-case complexity: O(log n)

Space Complexity:

The space complexity of the binary search is O(1).

 

We have listed out commonly asked interview questions that use the binary search algorithm:

  1. Find the number of rotations in a circularly sorted array.
  2. Find a given number’s first or last occurrence in a sorted array.
  3. Find the peak element in an array.
  4. Search in a nearly sorted array in logarithmic time.
  5. Find the smallest missing element from a sorted array.
  6. Find the floor and ceil of a number in a sorted integer array.
  7. Count occurrences of a number in a sorted array with duplicates.
  8. Find the floor and ceil of a number in a sorted array (Recursive solution).
  9. Find the frequency of each element in a sorted array containing duplicates.
  10. Ternary Search vs Binary search.
  11. Find the missing term in a sequence in logarithmic time.
  12. Find the square root of a number.
  13. Search an element in a circularly sorted array.
  14. Find the odd occurring element in an array in logarithmic time.
  15. Find pairs with difference `k` in an array | Constant Space Solution.
  16. Get the division of two numbers.
  17. Find the number of 1’s in a sorted binary array.
  18. Find `k` closest elements to a given value in an array.
  19. Exponential search.
  20. Find Minimum in Rotated Sorted Array.
  21. Find minimum size subarray sum in a given sorted array.
  22. Unbounded Binary Search.
  23. Find Kth Missing Positive Number.
  24. Find the Index of the Large Integer.
  25. Shortest Subarray to be Removed to Make Array Sorted.
  26. Minimum Operations to Make a Subsequence.

 

Recommended Articles for you: