Mastering Binary Search Algorithm [The Ultimate Guide]

This is the most complete guide on Binary Search Algorithm.

In this in-depth guide, you’ll learn:

What is Binary Search?
How does Binary Search work?
Binary Search Algorithm
Visual Representation of Binary Search Algorithm
Flowchart of the Binary search algorithm
Two different approach to implement the binary search algorithm
- Iterative Approach
- Recursive Approach

So, Let’s get started!

What is Binary Search?

Let’s try to understand about binary search from its name itself.

So, as the name indicates, Binary Search consists of two words. Right?

The first word i.e., Binary means two or something having two parts.

As, In the world of computer, Zero and One (i.e., 0 & 1) collectively called binary because it consists of two entity 0 and 1.

And,

Search means, to look over or inspect by exploring all the possible places to find or discover something: such as; to find a particular data item from a data set or from a list of data items, like array.

So, after combining these two words i.e., Binary and Search, we can say, It is an approach to find the position of a target (specific) value by dividing a list of data items (generally arrays) into two halves.

And, then the item (target value) is compared with the middle element of the list.

If the match is found, the location of the middle element is returned.

Otherwise, we search into either of the halves depending upon the result produced through the match.

If the target value is less than the middle element, the search is performed on the left half of the list.

And, If the target value is greater than the middle element, the search is performed on the right half of the list.

This process is repeated until the target value is found or determined to be absent or the search space is exhausted.

? Note: Binary search can be applied only on a sorted array or list of items. So, If the elements are not sorted already, we need to sort them first.

How does Binary Search work?

Let’s understand the working of binary search, step-by-step:

Variables we are using here:

start: Start index pointing to the first element of the array.
end: End index pointing to the last element of the array.
n: Total number of elements in the array. It also represents the size or length of the array.
key: The target/key element to be search.
mid: Middle index, which initially points to the middle element of the array.

The following algorithm is used to search an element in an array using binary search algorithm:

Binary Search Algorithm:

Step 01: Start
Step 02: Set the start index to the first element of the array, i.e., start = 0
Step 03: Set the end index to the last element of the array, i.e., end = n - 1
Step 04: Repeat Step 05 to Step 15 until start is less than or equal to the end index.
Step 05: Set middle index to start + (end - start) / 2.
Step 06: If arr[mid] == key
- Step 07: Return mid
- Step 08: Go to Step 18.
Step 09: [End of If ]
Step 10: else if arr[mid] < key
- Step 11: Set start = mid + 1
Step 12: [End of Else-If ]
Step 13: else
- Step 14: Set end = mid - 1
Step 15: [End of Else ]
Setp 16: [End of step 04 loop ]
Step 17: return -1 (If no match is found, or the search space is exhausted or if the start index exceeds the end index)
Step 18: Stop.

Now, before going into the detailed expalantion of the above algorithm, let’s first understand how to calculate the middle index efficiently.

You can also calculate the middle index by using this formula: i.e., mid = (start + end) / 2.

But, instead of using the above formula why am I using the formula: mid = start + (end - start) / 2. Right?

Answer: It’s only because, Let’s consider a scenario where the values of start and the end index are very large (nearly to the range of Integer data type).

For unsigned __int32 the Range of Values is 0 to 2³¹ – 1.

So, after adding these two values (i.e., start + end) may exceed the range of integers.

And, even if start and end are within the range, the sum overflows to a negative value for large arrays, and the value stays negative when divided by two. This causes an array index out of bounds with uncertain results.

So, to overcome from this problem, we are first subtracting the start index from the end index after that dividing this value by two and then adding it to the start index.

Now, let’s jump into the detailed explanation of the above algorithm.

Explanation of the above Algorithm:

In the above algorithm, step 2 and step 3 are self explanatory. Right?… As we are just creating two variables and initializing it with 0 and n - 1 respectively.

And, step 4 is basically the beginning of the while loop block which will run until the start index is less than or equal to the end index.

After that, inside the while block in the step 5, we are setting the value of the middle index which is equal to start + (end - start) / 2.

In step 6, we are comparing the value at the middle index with the target value, If the match is found, step 7 will execute and the location of the middle element is returned, after that the flow of execution goes to the step 18 and the If block will end in step 9.

In step 10, If the above If block does not satisfies the condition, and the value at the middle index is less than the target value, then we set the value of start as start = mid + 1.

Your question would be why?

Why we are setting the start as mid + 1? Right?

It’s only because, As we already know that the binary search will work only when the array is sorted. Right?

So, If the value at the middle index is less than the target value then it simply means, the target value will be on the right part of the array.

And, that’s why we are setting the start index to mid + 1.

So that, the half part can be ignored for the next iteration of the while loop.

After that, In the step 12, the else-if block will terminate.

Now, In step 13, if the else-if condition is not true then else block will execute.

And, In the else block, we are setting the end index to mid - 1.

The reason is very simple, if the else-if condition will not true then it simply means, the arr[mid] value is greater than target value.

So, there is no need to search in the right part of the array, and that’s why we are neglecting the right part.

Which means, If we set the end index to mid - 1, then we are automatically neglecting the right part of the array and the search will taken on the left part of the array.

After that, step 15 and step 16 are the end of else block and the while loop block respectively.

And, at the last step, In step 17, We are returning -1.

This step will execute only when If no match is found, or the search space is exhausted or if the start index exceeds the end index.

That’s it for all the steps of the above algorithm.

Visual Representation of Binary Search Algorithm:

Flowchart of the Binary search algorithm:

Now, let’s come to the implementation part of the binary search algorithm.

Basically, there are two different ways or approach to implement the binary search algorithm:

Iterative approach
Recursive approach

Let’s understand the above two approaches one-by-one:

Implementation of Iterative approach:

// writing a program in C++ for binary search in an array

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int n, int key) 
{
        
        int start = 0;   // starting index of the array
        int end = n - 1;    // ending index of the array
        
        while(start <= end)
        {
            int mid = start + (end - start) / 2;      // middle index of the array
            
            if(arr[mid] == key)
                return mid;
                
            else if(arr[mid] < key)
                start = mid + 1;
            
            else
                end = mid - 1;
        }
        return -1;
    }


int main()
{
    int arr[ ] = { 2, 5, 7, 8, 9, 13};

    int n = sizeof(arr) / sizeof(arr[0]);

    int key = 9;

    int result = binarySearch(arr, n, key);

    result == -1 ? cout << "Element not found"
                   : cout << "Element is present at index: "  << result;

   return 0;

};

If you compile and run the above program, it will produce the following result:

Output:

Element is present at index: 4

Implementation of Recursive approach:

// writing a program in C++ to implement recursive Binary Search

#include <bits/stdc++.h>
using namespace std;
 
int binarySearch(int arr[], int start, int end, int key)
{
    if (end >= start) {
        int mid = start + (end - start) / 2;
 
        if (arr[mid] == key)
            return mid;
 
        if (arr[mid] > key)
            return binarySearch(arr, start, mid - 1, key);
 
        return binarySearch(arr, mid + 1, end, key);
    }
    return -1;
}
 
int main()
{
    int arr[] = { 1, 7, 13, 16, 35 };
    int key = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, key);
    (result == -1)
        ? cout << "Element is not present in the array"
        : cout << "Element is present at index " << result;
    return 0;
};

If you compile and run the above program, it will produce the following result:

Output:

Element is not present in the array

Conclusion:

In this article, you learned all the things you need to know about “Binary Serach”, you also became familiar with the algorithm and flowchart of the Binary Search Algorithm.

So,

I really hope that you liked my article and got a lot of value from it.

Now, It’s your turn!

If you have any question, feel free to ask in the comment section below right now.

Share this Post