DSA-VerseLearn by watching code run
DashboardData StructuresAlgorithmsVisualizerCORECoding PlaygroundInterview QuestionsComplexity AnalyzerLearning NotesBookmarksLearning ProgressSettings
Searching algorithms

Searching

Binary Search

Searches a sorted array by repeatedly comparing the target with the middle element and discarding the half that cannot contain it.

Worst O(log n)Space O(1)
Open visualizer

1Detailed explanation

Binary search works on sorted data. It compares the target with the middle element: if they match we are done; if the target is larger, the whole left half (including mid) can be discarded; otherwise the right half is discarded.

Because the range halves every iteration, about log₂ n checks are enough — 20 checks cover a million elements.

The details matter: use low ≤ high as the loop condition, compute mid as low + (high − low) / 2 to avoid integer overflow in Java/C++/Go, and always move low/high past mid so the range shrinks.

2Pseudocode

procedure binarySearch(A, target)   // A is sorted
  low ← 0
  high ← length(A) − 1
  while low ≤ high
    mid ← low + ⌊(high − low) / 2⌋
    if A[mid] = target
      return mid
    else if A[mid] < target
      low ← mid + 1
    else
      high ← mid − 1
  return −1

3Interactive visualization

Binary Searchinteractive Open full visualizer
2
5
8
12
16
23
38
56
72
91
0
1
2
3
4
5
6
7
8
9
ComparingSwapping / movingCurrentSorted / finalFound / placed

Searches a sorted array by repeatedly comparing the target with the middle element and discarding the half that cannot contain it.

1 / 17

4Implementations

Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

const arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];
const target = 23;
console.log("Index of", target, "=", binarySearch(arr, target));

5Time and space complexity

Time
Best caseO(1)
Average caseO(log n)
Worst caseO(log n)
Space
AuxiliaryO(1)
InputO(n)
TotalO(n)

Time: Every iteration halves the search range [low, high]. Starting from n elements, after k iterations about n/2ᵏ remain, so at most ⌊log₂ n⌋ + 1 iterations are needed → O(log n). Best case: the first middle element is the target → O(1).

Space: The iterative version stores only low, high and mid → O(1) auxiliary space. (A recursive version would use O(log n) call-stack space.)

6Common interview variations

  • Lower bound / upper bound (first ≥ target, first > target).
  • First and last position of an element.
  • Search in a rotated sorted array.
  • Square root of x / binary search on the answer.
  • Find a peak element.

On this page

  1. 01Detailed explanation
  2. 02Pseudocode
  3. 03Interactive visualization
  4. 04Implementations (JS · Python · Java · Go)
  5. 05Time and space complexity
  6. 06Common interview variations