Binary Search
Binary Search eliminates half the remaining elements with every comparison by always checking the middle of the current search window. O(log n) — dramatically faster than Linear Search on large sorted arrays.
Search Target
↑ Set a target value above to begin searching the array
Legend
- • Bar height = element value
- • Faded bars = eliminated half
- • Dashed line = target level
- • L, M, H labels show pointers
Inspector
Legend
- • Bar height = element value
- • Faded bars = eliminated half
- • Dashed line = target level
- • L, M, H labels show pointers
Inspector
Reference implementation of Binary Search. Select a language tab to view and copy the code.
int binary_search(int arr[], int n, int target) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}#include <vector>
int binarySearch(const std::vector<int>& arr, int target) {
int left = 0, right = static_cast<int>(arr.size()) - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}public static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}def binary_search(arr: list[int], target: int) -> int:
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}Python — Code Walkthrough
Tuple unpacking for bounds
left, right = 0, len(arr) - 1Python multiple assignment initialises both bounds in one statement. right starts at the last valid index.
Floor division // for mid
mid = left + (right - left) // 2Python's // operator always floors (towards negative infinity), giving the lower-middle index for an even-length window. The subtraction form avoids overflow — though Python integers don't overflow, it is a good habit.
elif chain — three outcomes
if arr[mid] == target ... elif arr[mid] < target ... elsePython elif is cleaner than nested ifs. The three branches cover: found (return mid), target is right of mid (move left forward), target is left of mid (move right back).
Return -1 after the loop
return -1The while loop exits when left > right, meaning the search window is empty. Returning -1 signals that target was not found.