Binary Search – Iterative and Recursive Explained in Simple Words

Nidhi Sharma
4h
1.2k
0
0

Article

Introduction

Binary Search is one of the most important algorithms in DSA and a favorite in technical interviews. Many learners know the formula but struggle to understand why it works.

In simple words, binary search is about cutting the search space into half again and again instead of checking every element.

Real-World Meaning of Binary Search

Imagine searching for a word in a dictionary:

You never start from the first page
You open the middle page
If your word comes earlier, you move left
Otherwise, you move right

This is exactly how binary search works.

What is Binary Search?

Binary Search is a searching technique used to find an element in a sorted array.

Important rule:

The array must be sorted

Binary search works by repeatedly dividing the array into two halves and deciding which half to continue searching in.

Before vs After Understanding

Linear Search (Before)

Array: [1, 3, 5, 7, 9]
Search: 7
Steps: 1 → 3 → 5 → 7

Binary Search (After)

Array: [1, 3, 5, 7, 9]
Search: 7
Steps: 5 → 7

Binary search drastically reduces the number of steps.

Why Linear Search is Not Efficient

Linear search checks:

One element at a time
From start to end

For large data, this becomes slow.

Interviewers expect you to optimize using binary search.

What Interviewers Are Actually Testing

When binary search is asked, interviewers check:

Do you understand sorted data requirement?
Can you calculate mid safely?
Can you avoid infinite loops?

Key Idea of Binary Search (Very Simple)

At every step:

Compare target with middle element
If equal → answer found
If smaller → go left
If larger → go right

Step-by-Step Logic

Set low to start of array
Set high to end of array
Find mid
Compare arr[mid] with target
Reduce search space
Repeat until found or space is empty

Common Beginner Mistakes

Forgetting array must be sorted
Wrong mid calculation
Infinite loop due to incorrect conditions

One-Line Logic Before Code

Repeatedly cut the search space in half until the element is found.

Iterative Binary Search

C++ Code

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

    while (low <= high) {
        int mid = low + (high - low) / 2;

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

Recursive Binary Search

Idea in Simple Words

Instead of looping, the function calls itself on the left or right half.

C++ Code

int binarySearch(vector<int>& arr, int low, int high, int target) {
    if (low > high)
        return -1;

    int mid = low + (high - low) / 2;

    if (arr[mid] == target)
        return mid;
    else if (arr[mid] < target)
        return binarySearch(arr, mid + 1, high, target);
    else
        return binarySearch(arr, low, mid - 1, target);
}

Iterative vs Recursive Comparison

Feature	Iterative	Recursive
Space	O(1)	O(log n)
Simplicity	Easier	Conceptual
Interview Preference	High	Medium

Time and Space Complexity

Time Complexity: O(log n)
Space Complexity:
- Iterative: O(1)
- Recursive: O(log n)

Where Binary Search Is Used

Binary search is used in:

Finding elements in sorted data
Finding boundaries (first/last occurrence)
Optimization problems
Search space problems

Easy Summary (Explain Like I’m 10)

Binary search is like guessing a number where someone tells you higher or lower. Each time you guess, the options reduce by half. This makes finding things very fast compared to checking one by one.

Summary

Binary Search is a powerful searching algorithm that works on sorted data by repeatedly dividing the search space into halves. By understanding its real-world meaning, step-by-step logic, and both iterative and recursive approaches, you can solve many interview problems efficiently. Mastering binary search also prepares you for advanced search and optimization problems in DSA.