Searching Tested code in 3 languages

Binary Search, Visualized Step by Step

Check the middle of a sorted array, throw away the half that cannot hold your target, repeat. Press play to watch lo, mid and hi move, next to the exact line of code that runs.

Crio.Do · Last updated 18 November 2026

Interactive binary search Looking for 61

Look for 61 in indices 0–11. lo = 0, hi = 11.

0Comparisons
0Probes
1/–Step
def binary_search(a, target):    lo, hi = 0, len(a) - 1    while lo <= hi:        mid = (lo + hi) // 2        if a[mid] == target:            return mid        elif a[mid] < target:            lo = mid + 1        else:            hi = mid - 1    return -1

The highlighted line is the one the animation is running. This is the exact code we test.

Tip: use the arrow keys to step when the visualizer has focus. Try duplicates, a sorted list or your own numbers.

On this page
  1. How it works
  2. Worked example
  3. Complexity
  4. When to use it
  5. Common mistakes
  6. Interview questions
  7. FAQ
  8. Sources

How binary search works

Binary search finds a value in a sorted array by halving the search range at every step. Compare the target with the middle element. If the middle is smaller, the target can only be in the right half; if it is bigger, only in the left half. Every comparison throws away half of what is left.

It is the number-guessing game. Someone picks a number from 1 to 100 and answers "higher" or "lower". Guess 50, then 75 or 25, and so on. You never need more than 7 guesses, because 2⁷ = 128 is more than 100.

The code keeps two indices, lo and hi: the inclusive ends of the range that could still hold the target. The loop runs while lo <= hi. When lo passes hi, the range is empty, so the target is not in the array and the function returns -1.

The number worth remembering: an array of n elements needs at most ⌊log₂ n⌋ + 1 probes. For 1,000,000 elements that is 20 probes, against up to 1,000,000 checks for a linear scan.

The algorithm in 5 steps

  1. 1 Set lo = 0 and hi = n − 1.
  2. 2 While lo <= hi, take mid halfway between them, rounded down.
  3. 3 If a[mid] is the target, return mid.
  4. 4 If a[mid] is smaller, set lo = mid + 1; otherwise set hi = mid − 1.
  5. 5 If the loop ends, the target is not there: return -1.

Worked example

Here is every step of one search on a fixed array, generated by the same code as the visualizer.

Input: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], target23

  1. Step 1 Look for 23 in indices 0–9. lo = 0, hi = 9. 25812162338567291
  2. Step 2 The middle of 0–9 is index 4 (halfway, rounded down). 25812162338567291
  3. Step 3 a[4] is 16, not 23. 25812162338567291
  4. Step 4 16 < 23, so 23 can only be to the right. Drop indices 0–4. 25812162338567291
  5. Step 5 lo = 5. Keep searching indices 5–9. 25812162338567291
  6. Step 6 The middle of 5–9 is index 7 (halfway, rounded down). 25812162338567291
  7. Step 7 a[7] is 56, not 23. 25812162338567291
  8. Step 8 56 > 23, so 23 can only be to the left. Drop indices 7–9. 25812162338567291
  9. Step 9 hi = 6. Keep searching indices 5–6. 25812162338567291
  10. Step 10 The middle of 5–6 is index 5 (halfway, rounded down). 25812162338567291
  11. Step 11 a[5] is 23. That is the target. 25812162338567291
  12. Step 12 Found 23 at index 5. 25812162338567291

Result: index 5, after 3 probes and 5 comparisons. Searching the same array for 24 takes 4 probes and returns -1.

Time and space complexity

Best

O(1)

The target happens to be the first middle element.

Average

O(log n)

Each probe halves the range, so most searches take close to log₂ n probes.

Worst

O(log n)

At most ⌊log₂ n⌋ + 1 probes, including when the target is missing.

Space

O(1)

The loop only keeps lo, hi and mid. A recursive version uses O(log n) stack.

Needs sorted input:
Yes
Bounds:
Inclusive
Returns:
Index or -1
Duplicates:
Any match

The visualizer's array has 12 numbers, so no search on it can take more than 4 probes. Double the array and the limit grows by just one probe.

When to use it, and when not to

Good fit

  • Looking up values in a sorted array that changes rarely, such as a price list or a sorted ID table.
  • Finding boundaries: the first value ≥ x (lower bound) or the first value > x (upper bound), for range counts and insert positions.
  • "Binary search on the answer": when a yes/no check is monotonic, such as "can we ship everything in D days with capacity C?", search for the smallest C that works.
  • Debugging: git bisect is binary search over commits, finding the one that introduced a bug in about log₂ n test runs.

Pick something else when

  • The data is unsorted. Sorting first costs O(n log n), which only pays off if you will search many times.
  • The data changes often. Inserting into a sorted array is O(n); a balanced search tree keeps both lookups and inserts at O(log n).
  • You only need "is it there?". A hash set answers that in O(1) on average, with no sorting.

Common mistakes and bugs

  1. 1.while lo < hi with inclusive bounds

    With hi = n − 1, the loop must run while lo <= hi. Stopping at lo < hi skips the last remaining candidate, so a target sitting at that index is reported as missing.

  2. 2.Setting lo = mid or hi = mid

    When lo and hi are neighbours, mid equals lo, so lo = mid never moves and the loop spins forever. With inclusive bounds, always move past mid: mid + 1 or mid − 1.

  3. 3.(lo + hi) / 2 overflowing

    In Java, C and C++, lo + hi can exceed the integer range on very large arrays and go negative. Write lo + (hi − lo) / 2. Joshua Bloch reported in 2006 that this bug sat in Java's own Arrays.binarySearch for about nine years. Python integers do not overflow.

  4. 4.Searching unsorted input

    Binary search does not check that its input is sorted. On unsorted data it silently returns -1 for values that are there, or finds the wrong one. Sort first, or keep the data sorted on insert.

  5. 5.Expecting the first match among duplicates

    The standard version returns whichever matching index it lands on first. If you need the first occurrence, use the lower-bound variant: on a match, record it and keep searching left.

Interview questions

Try answering before you open the model answer.

Q1 Find the first and last position of a target in a sorted array with duplicates.

Model answer: Run two boundary searches. The first finds the smallest index with a[i] >= target; the second finds the smallest index with a[i] > target, and the last position is that index minus one. If the first index is out of range or does not hold the target, return [-1, -1]. Both are O(log n).

Q2 Search for a target in a rotated sorted array.

Model answer: At any mid, at least one half is sorted. Check which half is sorted by comparing a[lo] with a[mid], then check whether the target lies inside that sorted half's range. If it does, search there; otherwise search the other half. This is O(log n) when values are distinct.

Q3 Why write mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2?

Model answer: In languages with fixed-size integers, lo + hi can overflow when both are large, producing a negative mid and an out-of-bounds read. lo + (hi - lo) / 2 computes the same value without overflow. In Python it does not matter, but interviewers like to hear that you know why.

Q4 Compute the integer square root of n without a library.

Model answer: Binary search on the answer. Search m in [0, n] for the largest m with m × m <= n. If mid × mid <= n, record mid and go right; otherwise go left. That takes O(log n) steps.

Q5 Find the minimum ship capacity to deliver all packages within D days.

Model answer: Binary search on the capacity, between the heaviest package and the sum of all weights. For a candidate capacity, simulate greedily in O(n) to count the days needed. Feasibility is monotonic, so find the smallest capacity that fits in D days: O(n log(sum of weights)).

Frequently asked questions

Does binary search work on unsorted arrays?

No. It assumes that everything left of the middle is smaller and everything right is bigger. On unsorted data that assumption is false, so it can miss values that are present or return a wrong index, without any error. Sort the array first, or use a linear search or a hash set.

What is the time complexity of binary search?

O(log n) in the average and worst case, and O(1) in the best case, when the first middle element is the target. Each probe halves the remaining range, so an array of n elements needs at most ⌊log₂ n⌋ + 1 probes. The iterative version uses O(1) extra space.

Which index does binary search return when there are duplicates?

The standard version, shown here, returns whichever matching index it reaches first, which may not be the first occurrence. Java's Arrays.binarySearch documents the same: no guarantee which match is found. For the first occurrence, use a lower-bound search, such as Python's bisect_left, and check the value.

Should I write binary search recursively or iteratively?

Iteratively, in most cases. The loop version uses O(1) extra space, avoids recursion limits and is just as short. The recursive version is fine for explaining the idea, and the recursion depth is only about log₂ n, but it adds function-call overhead without making the code any clearer.

Is there a built-in binary search in Python, Java and JavaScript?

Python has the bisect module (bisect_left and bisect_right) for lower and upper bounds. Java has Arrays.binarySearch and Collections.binarySearch. JavaScript has no built-in binary search for arrays, so you write your own, like the version on this page, or use a library.

Crio Software Development

Go from watching algorithms to using them

Crio's Software Development Fellowship has you practise data structures and algorithms by building real projects, the way they come up at work and in interviews. Start with a free trial session.

Explore the program

Free trial · No credit card required

Sources

  1. Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed., 1998)
    Section 6.2.1, Searching an ordered table.
  2. Joshua Bloch, "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken", Google Research blog, 2 June 2006
    The (lo + hi) / 2 overflow bug.
  3. Java SE 21 API: java.util.Arrays
    binarySearch documents that with duplicates there is no guarantee which match is found.
  4. Python documentation: bisect, array bisection algorithm
    bisect_left and bisect_right.

The animation, the worked example and the step counts are all generated by one implementation of binary search, which is unit-tested against an independent version on edge cases and hundreds of random inputs. The Python, Java and JavaScript code is the exact code shown above, run on the same cases.

Last updated:

More algorithms, visualized

Every page runs real, tested code and lets you step through it with your own input.

All algorithms