Binary Search (Iterative) - C++ Program

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

#include <iostream>

This header provides:

cout for displaying output
cin for taking input from the user

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) {
        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

}

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.

Output