C++ Program for Binary Search with Example and Explanation

A C++ program for binary search uses a loop to repeatedly divide the sorted array and check the middle element with while (low <= high) and updates low or high until the target is found or not; example: int binarySearch(int arr[], int size, int target) { int low = 0, high = 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; }.

Examples

Inputarr = {1, 3, 5, 7, 9}, target = 5

Output2

Inputarr = {2, 4, 6, 8, 10}, target = 1

Output-1

Inputarr = {10, 20, 30, 40, 50}, target = 50

Output4

How to Think About It

To do binary search, first think of the array as a sorted list of books on a shelf. You look at the middle book and compare it to the one you want. If the middle book is the one, you stop. If the book you want is bigger, you look only in the right half; if smaller, only in the left half. You keep doing this until you find the book or run out of books.

Algorithm

1

Start with two pointers: low at the start, high at the end of the array.

2

While low is less than or equal to high:

3

Calculate mid as the middle index between low and high.

4

If the element at mid equals the target, return mid.

5

If the element at mid is less than the target, move low to mid + 1.

6

Else, move high to mid - 1.

7

If the target is not found, return -1.

Code

cpp

#include <iostream>
using namespace std;

int binarySearch(int arr[], int size, int target) {
    int low = 0, high = 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;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    int result = binarySearch(arr, size, target);
    cout << result << endl;
    return 0;
}

Output

2

Dry Run

Let's trace searching for 5 in the array {1, 3, 5, 7, 9} through the code.

1

Initialize pointers

low = 0, high = 4 (array indices)

2

Calculate mid

mid = 0 + (4 - 0) / 2 = 2

3

Compare arr[mid] with target

arr[2] = 5 equals target 5, return 2

low	high	mid	arr[mid]	comparison
0	4	2	5	arr[mid] == target, return 2

Why This Works

Step 1: Divide and conquer

The code splits the search space in half each time using mid, which makes searching faster than checking every element.

Step 2: Adjust search range

If the middle element is less than the target, the code moves low up to search the right half; otherwise, it moves high down to search the left half.

Step 3: Stop condition

The loop stops when low passes high, meaning the target is not in the array, and returns -1.

Alternative Approaches

Recursive binary search

cpp

#include <iostream>
using namespace std;

int binarySearchRecursive(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 binarySearchRecursive(arr, mid + 1, high, target);
    else return binarySearchRecursive(arr, low, mid - 1, target);
}

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    int result = binarySearchRecursive(arr, 0, size - 1, target);
    cout << result << endl;
    return 0;
}

Uses function calls instead of a loop; easier to read but uses more memory for call stack.

Using std::binary_search (C++ STL)

cpp

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

int main() {
    int arr[] = {1, 3, 5, 7, 9};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 5;
    bool found = binary_search(arr, arr + size, target);
    cout << (found ? "Found" : "Not Found") << endl;
    return 0;
}

Simplifies code by using built-in function but does not return index.

Complexity: O(log n) time, O(1) space

Time Complexity

Binary search divides the search space in half each step, so it runs in logarithmic time, O(log n), where n is the number of elements.

Space Complexity

The iterative version uses constant extra space O(1) because it only stores a few variables.

Which Approach is Fastest?

Iterative binary search is fastest and uses less memory than recursive. Using std::binary_search is convenient but does not give the index.

Approach	Time	Space	Best For
Iterative Binary Search	O(log n)	O(1)	Fastest, low memory
Recursive Binary Search	O(log n)	O(log n)	Clear code, uses call stack
std::binary_search (STL)	O(log n)	O(1)	Quick check if element exists