Loading algorithms…

Loading visualizer…

Algorithms/Searching/Binary Search

Binary Search

Halve the search space at every step on a sorted array. The canonical O(log n) search algorithm — best case finds in 1 comparison, worst case in ⌈log₂(n+1)⌉.

SearchingDivide & ConquerSorted ArrayLogarithmic
Comparisonsso far
0
Targetlooking for
42
Resultoutcome
—

Sorted Array

Cyan = lo · Amber = mid · Rose = hi · Emerald = found · dimmed = eliminated

3[0]
6[1]
9[2]
12[3]
15[4]
18[5]
21[6]
24[7]
27[8]
30[9]
33[10]
36[11]
39[12]
42[13]
45[14]
48[15]
Legend:lomidhifoundeliminated

Comparison log

Every arr[mid] vs target comparison in order

No comparisons yet. Press Play or step forward.

1 / 0
Speed
n16
binary-search.js
1function binarySearch(arr, target) {
2 let lo = 0;
3 let hi = arr.length - 1;
4 
5 while (lo <= hi) {
6 const mid = Math.floor((lo + hi) / 2);
7 const value = arr[mid];
8 
9 if (value === target) {
10 return mid; // found
11 }
12 
13 if (value < target) {
14 lo = mid + 1; // search right half
15 } else {
16 hi = mid - 1; // search left half
17 }
18 }
19 
20 return -1; // not found
21}

Algorithm Explanation

Binary search is the canonical divide and conquer search algorithm. Given a sorted array, it repeatedly halves the search space by comparing the target to the middle element. If the target is smaller, search the left half; if larger, search the right half. At most ⌈log₂(n+1)⌉ comparisons are needed.

⚙️ How It Works

  1. Maintain two pointers: lo (start of the search range) and hi (end of the search range). Initially lo = 0 and hi = n - 1.
  2. Compute the midpoint: mid = ⌊(lo + hi) / 2⌋. Read arr[mid].
  3. Compare arr[mid] to the target:
    • Equal → return mid (found).
    • Smaller than target → set lo = mid + 1 (search the right half).
    • Larger than target → set hi = mid - 1 (search the left half).
  4. Repeat until lo > hi. At that point the search range is empty and the target is not present.

🔢 Worked Example

// Search for 23 in [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25]
lo=0, hi=12, mid=6 → arr[6]=13 → go right
lo=7, hi=12, mid=9 → arr[9]=19 → go right
lo=10, hi=12, mid=11 → arr[11]=23 = target
→ Found at index 11 (3 comparisons)

💡 Sorted input is mandatory. Binary search on an unsorted array is meaningless — the comparison rules (go left / go right) rely on the array being sorted in non-decreasing order. Use merge sort (O(n log n)) or insertion sort (O(n) on nearly-sorted data) to sort first.

⚖️ Binary vs Linear vs Hash

Binary search (this page)
  • O(log n) time, O(1) space.
  • Requires sorted input.
  • Great cache locality.
  • Insertions are expensive — O(n) to maintain sortedness.
Linear search
  • O(n) time, O(1) space.
  • Works on any data (sorted or not).
  • Branch-free / vectorisable in low-level code.
  • Beats binary search on tiny n (n < ~20).
Hash-based lookup
  • O(1) average time, O(n) space.
  • Inserts are O(1) average too.
  • No ordering — can't find "next larger" or range queries.
  • Used by dicts, sets, hash maps everywhere.
←Previous Algorithm
Radix Sort
SortingO(d·(n+k))
Next Algorithm→
Linear Search
O(n)Searching

Binary search requires the array to be sorted. Every iteration halves the search space, so at most ⌈log₂(n+1)⌉ comparisons are needed.