Binary Search

Binary search is like the guessing game where you always pick the middle number and are told higher or lower, cutting the possibilities in half every time.

In this page:

What is Binary Search
How It Works
Search Boundaries
Complexity
Common Variation

Syntax

markup

low, high = 0, len(arr) - 1
while low <= high:
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        low = mid + 1
    else:
        high = mid - 1
return -1

What is Binary Search

Binary search finds a target value in sorted data by repeatedly checking the middle element and eliminating half of the remaining range based on whether the target is smaller or larger — this only works because the data is sorted, which lets you rule out an entire half without checking it.

Example: What is Binary Search

#include <iostream>
using namespace std;
int main() {
	int arr[] = {1, 3, 5, 7, 9, 11};
	int target = 7, low = 0, high = 5;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (arr[mid] == target) { cout << "Found at index " << mid; break; }
		else if (arr[mid] < target) low = mid + 1;
		else high = mid - 1;
	}
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {1, 3, 5, 7, 9, 11};
		int target = 7, low = 0, high = 5;
		while (low <= high) {
			int mid = (low + high) / 2;
			if (arr[mid] == target) { System.out.println("Found at index " + mid); break; }
			else if (arr[mid] < target) low = mid + 1;
			else high = mid - 1;
		}
	}
}

arr = [1, 3, 5, 7, 9, 11]
target = 7
low, high = 0, 5
while low <= high:
    mid = (low + high) // 2
    if arr[mid] == target:
        print("Found at index", mid)
        break
    elif arr[mid] < target:
        low = mid + 1
    else:
        high = mid - 1

#include <stdio.h>
int main() {
	int arr[] = {1, 3, 5, 7, 9, 11};
	int target = 7, low = 0, high = 5;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (arr[mid] == target) { printf("Found at index %d", mid); break; }
		else if (arr[mid] < target) low = mid + 1;
		else high = mid - 1;
	}
	return 0;
}

How It Works

At each step, compare the target to the value at the midpoint of the current range: if they match, you're done; if the target is smaller, discard the right half and search the left half; if larger, discard the left half and search the right half.

Example: How It Works

#include <iostream>
using namespace std;
int main() {
	int arr[] = {1, 3, 5, 7, 9, 11};
	int target = 3, low = 0, high = 5;
	while (low <= high) {
		int mid = (low + high) / 2;
		cout << "mid=" << mid << " value=" << arr[mid] << endl;
		if (arr[mid] == target) break;
		else if (arr[mid] < target) low = mid + 1;
		else high = mid - 1;
	}
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {1, 3, 5, 7, 9, 11};
		int target = 3, low = 0, high = 5;
		while (low <= high) {
			int mid = (low + high) / 2;
			System.out.println("mid=" + mid + " value=" + arr[mid]);
			if (arr[mid] == target) break;
			else if (arr[mid] < target) low = mid + 1;
			else high = mid - 1;
		}
	}
}

arr = [1, 3, 5, 7, 9, 11]
target = 3
low, high = 0, 5
while low <= high:
    mid = (low + high) // 2
    print("mid=", mid, "value=", arr[mid])
    if arr[mid] == target:
        break
    elif arr[mid] < target:
        low = mid + 1
    else:
        high = mid - 1

#include <stdio.h>
int main() {
	int arr[] = {1, 3, 5, 7, 9, 11};
	int target = 3, low = 0, high = 5;
	while (low <= high) {
		int mid = (low + high) / 2;
		printf("mid=%d value=%d\n", mid, arr[mid]);
		if (arr[mid] == target) break;
		else if (arr[mid] < target) low = mid + 1;
		else high = mid - 1;
	}
	return 0;
}

Search Boundaries

Two pointers, typically called low and high, mark the current search range's boundaries; the midpoint is calculated between them each step, and after eliminating half the range, one of the two boundaries moves to shrink the range for the next comparison.

Example: Search Boundaries

#include <iostream>
using namespace std;
int main() {
	int low = 0, high = 5;
	int mid = (low + high) / 2;
	cout << "low=" << low << " high=" << high << " mid=" << mid;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int low = 0, high = 5;
		int mid = (low + high) / 2;
		System.out.println("low=" + low + " high=" + high + " mid=" + mid);
	}
}

low, high = 0, 5
mid = (low + high) // 2
print("low=", low, "high=", high, "mid=", mid)

#include <stdio.h>
int main() {
	int low = 0, high = 5;
	int mid = (low + high) / 2;
	printf("low=%d high=%d mid=%d", low, high, mid);
	return 0;
}

Complexity

Binary search takes O(log n) time because each comparison halves the remaining search space, and O(1) extra space when done iteratively with just the two boundary pointers — a dramatic improvement over linear search's O(n) on large sorted datasets.

Example: Complexity

#include <iostream>
using namespace std;
int main() {
	cout << "Binary search: O(log n) time, O(1) extra space when done iteratively";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Binary search: O(log n) time, O(1) extra space when done iteratively");
	}
}

print("Binary search: O(log n) time, O(1) extra space when done iteratively")

#include <stdio.h>
int main() {
	printf("Binary search: O(log n) time, O(1) extra space when done iteratively");
	return 0;
}

Common Variation

When the sorted data contains duplicate values, a standard binary search may land on any one of the matching elements — a common variation adjusts the comparison logic to specifically find the first (or last) occurrence of the target instead of just any match.

Example: Common Variation

#include <iostream>
using namespace std;
int main() {
	cout << "With duplicates, a standard binary search may land on any matching index, not necessarily the first or last";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("With duplicates, a standard binary search may land on any matching index, not necessarily the first or last");
	}
}

print("With duplicates, a standard binary search may land on any matching index, not necessarily the first or last")

#include <stdio.h>
int main() {
	printf("With duplicates, a standard binary search may land on any matching index, not necessarily the first or last");
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Linear Search Next Lesson → Binary Search on Answer