Binary Search (Iterative) in C++

Binary Search Algorithm in C++ (Iterative Implementation).

BeginnerSorting & Searching ProgramsExample 10 of 13

binary-search-iterative.cpp

1#include <iostream>
2using namespace std;
3
4int binarySearch(int arr[], int n, int key) {
5    int left = 0;
6    int right = n - 1;
7    
8    while (left <= right) {
9        int mid = left + (right - left) / 2;
10        
11        if (arr[mid] == key) {
12            return mid;  // Found at index mid
13        }
14        
15        if (arr[mid] < key) {
16            left = mid + 1;  // Search right half
17        } else {
18            right = mid - 1;  // Search left half
19        }
20    }
21    
22    return -1;  // Not found
23}
24
25int main() {
26    int arr[] = {11, 12, 22, 25, 34, 64, 90};
27    int n = sizeof(arr) / sizeof(arr[0]);
28    int key;
29    
30    cout << "Sorted array: ";
31    for (int i = 0; i < n; i++) {
32        cout << arr[i] << " ";
33    }
34    cout << endl;
35    
36    cout << "Enter element to search: ";
37    cin >> key;
38    
39    int result = binarySearch(arr, n, key);
40    
41    if (result != -1) {
42        cout << "Element found at index: " << result << endl;
43    } else {
44        cout << "Element not found in array" << endl;
45    }
46    
47    return 0;
48}

Output

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

What's going on

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.

Header File Used

This header provides:

cout for displaying output

cin for taking input from the user

1#include <iostream>

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

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

}

1return 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

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

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 ✓

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

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

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

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

return 0;

This ends the program successfully.

PreviousLinear Search NextBinary Search (Recursive)