Binary Search

Classic binary search for finding a target value in a sorted array in O(log n).

[Binary Search]|

Jul 9, 2026

|explanatory_notes.md|

#binary-search#sorted-array#search

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;

int binarySearch(vector<int>& a, int target) {
    int l = 0, r = (int)a.size() - 1;
    while (l <= r) {
        int m = l + (r - l) / 2;
        if (a[m] == target) return m;
        if (a[m] < target) l = m + 1;
        else r = m - 1;
    }
    return -1;
}

13 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

Binary Search

Finds a target value in a sorted array by repeatedly halving the search interval.

How It Works

Compare midpoint to target

If equal, return index

If midpoint

<

target, search right half

If midpoint

>

target, search left half

Return

-1

if not found

Overflow Safety

Midpoint computed as $m = l + \lfloor(r - l) / 2\rfloor$ instead of $\lfloor(l + r) / 2\rfloor$ to avoid integer overflow.

When to Use

Searching in a sorted array

Finding exact match

Complexity

Time —

O(\log n)

Space —

O(1)