For the best experience, we recommend using a widescreen desktop

Binary Search

Efficiently finds an element in a sorted array by halving the search space.

Target:11

Step 1 of 7

Binary Search for target = 11 in a sorted array of 9 elements.

Comparisons

▶Algorithm

BinarySearch(arr, target):
lo = 0; hi = n−1
while lo ≤ hi:
mid = (lo + hi) / 2
if arr[mid] == target: return mid
if arr[mid] < target: lo = mid+1
else: hi = mid−1
return −1  // not found

Legend

Mid element

Search window

Found

Out of range

1 / 7Speed