Skip to content
Binary Search Algorithm C++

Binary Search Algorithm

The Binary Search Algorithm, a simple and faster search. But on one condition, we need a sorted array or sort the given array before we perform a binary search.

Why Binary Search?

We can use linear search for smaller numbers but, when having hundreds, and thousands, to compare, it would be inefficient to compare every number, taking a lot of time.

Binary Search Working

In simple terms, the binary search follows the Divide and Conquer method. First, we take a sorted array, then we compare the element to be searched with the middle element of the array to know whether it’s greater or smaller. If it is small, we are sure we can find it in the first half else look for it in the second half and so on, till we find the element repeat the whole process again.

Pseudocode

  1. Given, a sorted array
  2. Next, take the element to be searched
  3. Now compare it with the middle element of the array
  4. If it is less than that, consider the first half of the array and repeat from step 3
  5. Else if it’s greater than the given element look in the second half
  6. Repeat the above steps until the element is found.

Binary Search Program

Code in C++

#include <iostream>
using namespace std;

int BinarySearch(int array[], int s, int low, int high)
{
    //when low = mid we finished our search
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (array[mid] == s)
            return mid;
        //less than mid
        if (array[mid] < s)
            low = mid + 1;
        //greater than mid
        else
            high = mid - 1;
    }
    return -1;
}

int main()
{
    int array[] = {1, 4, 5, 8, 10, 11, 20};
    int n = sizeof(array) / sizeof(array[0]);
    int s = 5;
    int answer = BinarySearch(array, s, 0, n - 1);
    if (answer == -1)
       cout<<"Element Not Found";
    else
        cout<<"Element "<<array[answer]<<" found at "<<answer;
        return 0;
}

Time Complexity: O(log n)

Space Complexity: O(n)

Conclusion

I also wrote an article on Linear Search, do you know it’s time & space complexity? read it here – Linear Search. This post is part of my #30DaysChallenge to write a blog post every day on what I learn, Happy Coding ~ Abhiram Reddy.

Tags: