Sri Charan Tokachichu

Posted on Mar 23

Binary Search Template Every Programmer Should Know (Beginner-Friendly)

#programming #dsa #cpp #algorithms

Introduction

Binary Search is one of the most important algorithms in Data Structures and Algorithms.

It helps us search efficiently in a sorted array.

Instead of checking every element one by one, Binary Search reduces the search space by half each time, making it very fast.

When to Use Binary Search?

You can use Binary Search when:

The array is sorted
You need to find an element or a condition
You want better performance than linear search

Basic Idea

In Binary Search:

Find the middle element
Compare it with the target
If equal → return index
If target is smaller → search left side
If target is larger → search right side

Example

Array:

[1, 3, 5, 7, 9]

Target = 5

Steps:

Middle element = 5
Target found ✅

Binary Search Template (C++)

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;

    while(left <= right) {
        int mid = left + (right - left) / 2;

        if(arr[mid] == target)
            return mid;
        else if(arr[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;
}

int main() {
    vector<int> arr = {1,3,5,7,9};
    int target = 5;

    cout << binarySearch(arr, target);
    return 0;
}

Time Complexity

Time Complexity: O(log n)
Space Complexity: O(1)

Binary Search is much faster than linear search for large inputs because it reduces the search space by half in every step.

Common Mistakes

Using Binary Search on unsorted arrays
Wrong mid calculation (can cause overflow)
Incorrect loop conditions leading to infinite loops

Where is Binary Search Used?

Binary Search is used in many problems like:

Searching in sorted arrays
Finding first or last occurrence
Peak element problems
Search in rotated sorted array

Quick Checklist Before Coding

Is the array sorted?
Are you using correct left <= right condition?
Are you updating left and right properly?
Are you calculating mid safely?

Practice Problems (Highly Recommended)

To master Binary Search, try solving these problems:

Pro Tip

Binary Search is not just about searching in arrays.

Many problems use Binary Search on the answer space (also called "Binary Search on Answer").

Practicing these problems will help you understand different patterns of Binary Search.

Conclusion

Binary Search is a must-know algorithm for coding interviews and competitive programming.

Once you understand the template, you can apply it to many problems easily.

Practicing Binary Search will greatly improve your problem-solving skills.

DEV Community