Binary Search (Iterative)

Binary Search Algorithm in C++ (Iterative Implementation)

BeginnerTopic: Sorting & Searching Programs

C++ Binary Search (Iterative) Program

This program helps you to learn the fundamental structure and syntax of C++ programming.

#include <iostream>
using namespace std;

int binarySearch(int arr[], int n, int key) {
    int left = 0;
    int right = n - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == key) {
            return mid;  // Found at index mid
        }
        
        if (arr[mid] < key) {
            left = mid + 1;  // Search right half
        } else {
            right = mid - 1;  // Search left half
        }
    }
    
    return -1;  // Not found
}

int main() {
    int arr[] = {11, 12, 22, 25, 34, 64, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key;
    
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    cout << "Enter element to search: ";
    cin >> key;
    
    int result = binarySearch(arr, n, key);
    
    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found in array" << endl;
    }
    
    return 0;
}

Output

Sorted array: 11 12 22 25 34 64 90
Enter element to search: 25
Element found at index: 3

Understanding Binary Search (Iterative)

This program teaches you how to implement the Binary Search algorithm in C++ using an iterative approach. Binary Search is a highly efficient divide-and-conquer algorithm that searches a sorted array by repeatedly dividing the search interval in half. It's much faster than Linear Search for large datasets, but requires the array to be sorted first.

---

1. What This Program Does

The program searches for an element in a sorted array using Binary Search (iterative version). For example:

•Sorted array: [11, 12, 22, 25, 34, 64, 90]

•Search for: 25

•Result: Element found at index 3

Binary Search eliminates half of the remaining elements in each step, making it extremely efficient.

---

2. Header File Used

This header provides:

•cout for displaying output

•cin for taking input from the user

---

#include <iostream>

3. Understanding Binary Search

Algorithm Concept

•Requires sorted array

•Compare target with middle element

•If equal: found

•If target < middle: search left half

•If target > middle: search right half

•Repeat until found or interval empty

Visual Example

Array: [11, 12, 22, 25, 34, 64, 90]

Search for: 25

Step 1: left=0, right=6, mid=3

•arr[3] = 25 → match! Found at index 3

Example (searching for 34):

Step 1: left=0, right=6, mid=3

•arr[3] = 25 < 34 → search right half

Step 2: left=4, right=6, mid=5

•arr[5] = 64 > 34 → search left half

Step 3: left=4, right=4, mid=4

•arr[4] = 34 → match! Found at index 4

---

4. Function: binarySearch()

int binarySearch(int arr[], int n, int key) {

int left = 0;

int right = n - 1;

while (left <= right) {

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

if (arr[mid] == key) {

}

if (arr[mid] < key) {

left = mid + 1; // Search right half

} else {

right = mid - 1; // Search left half

}

return -1; // Not found

}

            return mid;  // Found at index mid

How it works

•Maintains search interval [left, right]

•Calculates middle index: mid

•Compares arr[mid] with key

•Adjusts interval based on comparison

•Continues until found or interval empty

---

5. Step-by-Step Algorithm

Step 1: Initialize Interval

•left = 0 (start of array)

•right = n - 1 (end of array)

Step 2: Calculate Middle

•mid = left + (right - left) / 2

•Prevents integer overflow

•Better than (left + right) / 2

Step 3: Compare

•If arr[mid] == key: found, return mid

•If arr[mid] < key: key in right half, set left = mid + 1

•If arr[mid] > key: key in left half, set right = mid - 1

Step 4: Repeat

•Continue while left <= right

•Interval shrinks by half each iteration

•If left > right: key not found, return -1

---

6. Understanding Mid Calculation

Why left + (right - left) / 2?

•Prevents integer overflow

•(left + right) might overflow for large values

•left + (right - left) / 2 is equivalent but safer

Example

•left = 1000000, right = 2000000

•(left + right) / 2 might overflow

•left + (right - left) / 2 = 1000000 + 500000 = 1500000 ✓

---

7. Time and Space Complexity

Time Complexity

: O(log n)

•Each iteration eliminates half the elements

•Maximum iterations: log₂(n)

•Example: n=1000 → ~10 iterations

•Example: n=1000000 → ~20 iterations

Space Complexity

: O(1)

•Only uses constant extra space

•No recursion stack (iterative version)

•Only variables: left, right, mid

---

8. When to Use Binary Search

Best For

•Sorted arrays

•Large datasets

•Frequent searches

•When O(log n) performance is needed

•Search operations are common

Not Recommended For

•Unsorted arrays (must sort first)

•Small arrays (Linear Search might be simpler)

•When array changes frequently (sorting overhead)

•When insertion/deletion is common

---

9. Important Considerations

Array Must Be Sorted

•Binary Search only works on sorted arrays

•Sort array first if unsorted

•Ascending or descending order (adjust comparison)

Loop Condition

•left <= right: includes both endpoints

•When left > right: interval is empty, key not found

•Important for correct termination

Index Updates

•left = mid + 1: exclude mid (already checked)

•right = mid - 1: exclude mid (already checked)

•Prevents infinite loops

---

10. Advantages Over Linear Search

Performance

•O(log n) vs O(n)

•For n=1000000: ~20 comparisons vs ~500000 comparisons

•Dramatically faster for large arrays

Efficiency

•Eliminates half elements each step

•Logarithmic growth vs linear growth

---

11. return 0;

This ends the program successfully.

---

Summary

•Binary Search divides search interval in half each iteration.

•Time complexity: O(log n) - extremely efficient for large arrays.

•Space complexity: O(1) - only uses constant extra space (iterative version).

•Requires sorted array - must sort first if unsorted.

•Iterative implementation avoids recursion stack overhead.

•Mid calculation: left + (right - left) / 2 prevents overflow.

•Much faster than Linear Search for large datasets.

•Understanding Binary Search is essential for efficient searching.

This program is fundamental for beginners learning efficient search algorithms, understanding divide-and-conquer techniques, and preparing for advanced searching methods in C++ programs.

Let us now understand every line and the components of the above program.

Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.

Practical Learning Notes for Binary Search (Iterative)

This C++ program is part of the "Sorting & Searching Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.

A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.

For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.

Binary Search (Recursive)

Linear Search