Coding interview problems › Binary Search

🔍 Binary Search Easy

Binary Search

Binary search explained for interviews: halve a sorted array each step, avoid the off-by-one traps, tested Python code and an interactive visual.

Also searched as: binary search algorithm in Python · search in a sorted array · iterative binary search

🔍

Try it live Free

Binary Search

Pick a target and watch the search space halve on every look, so 16 elements need at most 4 comparisons, and try the off-by-one traps the lab highlights.

Also useful: Big-O Complexity

Open the playground →

The problem

You are given a list of integers sorted in increasing order and a target. Return the index of target if it is present, otherwise return -1. Aim for O(log n) time.

Inputnums = [-3, 0, 4, 7, 12], target = 7
Output3
Inputnums = [-3, 0, 4, 7, 12], target = 5
Output-1

5 would sit between 4 and 7, but it is not there.

The key insight

Because the list is sorted, one comparison with the middle element tells you which half cannot contain the target. Throw that half away and repeat. Each look halves the search space, so even a million elements need only about 20 looks.

Brute force first: Scanning every element from left to right works but takes O(n) time and ignores the fact that the data is sorted.

Step-by-step approach

  1. Keep two indices, lo = 0 and hi = len(nums) - 1, marking the part of the list that could still hold the target.
  2. While lo <= hi, compute mid = (lo + hi) // 2.
  3. If nums[mid] equals the target, return mid.
  4. If nums[mid] is smaller than the target, the answer must be to the right: set lo = mid + 1.
  5. Otherwise it must be to the left: set hi = mid - 1.
  6. If the loop ends, the range is empty and the target is absent: return -1.

Python solution

PYTHON 3tested
def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:                 # range [lo, hi] is still non-empty
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1            # target can only be right of mid
        else:
            hi = mid - 1            # target can only be left of mid
    return -1

Complexity

TimeO(log n)
SpaceO(1)

Every iteration halves the size of the range [lo, hi], so the loop runs at most about log2(n) + 1 times. Only two indices are stored.

Common mistakes

Frequently asked questions

What is the time and space complexity of binary search?

Iterative binary search runs in O(log n) time because the range halves every step, and it uses O(1) extra space. A recursive version also takes O(log n) time but uses O(log n) stack space.

Why is mid written as lo + (hi - lo) // 2 in some solutions?

In languages with fixed-size integers such as C++ or Java, lo + hi can overflow for very large indices. Python integers do not overflow, so (lo + hi) // 2 is safe here, but the other form is a good habit in interviews.

What if the array has duplicates?

Plain binary search returns some matching index, not necessarily the first or last. To get the first or last occurrence, keep searching left or right after a match, as in the first-and-last-position problem.

Should I use Python's bisect module?

bisect_left and bisect_right are correct and fast, and are fine in online assessments. In an interview, write the loop yourself first, since the boundary logic is what is being tested.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Binary Search Binary Search lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.