Binary Search

Q: What is the time complexity of binary search?

O(log n) . Every comparison halves the range that can still hold the target, so after k steps at most n / 2^k candidates remain. A list of 10^4 elements needs at most 14 comparisons, and a list of 10^9 elements at most 30. The iterative version uses O(1) extra space.

Q: Why does binary search need a sorted array?

The step that discards half the list relies on order. When nums[mid] < target , sorting guarantees that every element left of mid is also smaller than target , so none of them can match. In an unsorted list that comparison says nothing about the other elements, and you have to check them all.

Q: Should binary search be iterative or recursive?

Both are correct and both run in O(log n) time. The recursive version calls itself on one half and uses O(log n) stack space; the iterative version moves lo and hi in a loop and uses O(1) . Interviewers usually expect the loop, and it avoids any recursion limit.

Q: How do you avoid overflow when computing the middle index?

Write mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2 . Both give the same index, but the second form adds two indexes first, and in a 32-bit integer that sum overflows once the indexes pass about 1.07 × 10^9 . Python and Ruby have unbounded integers, so there the short form is safe.

EasyBinary search

+10

You get a list of integers nums sorted in increasing order, with no value repeated, and an integer target. Return the index of target in nums, counting from 0, or -1 if it is not in the list. Aim for O(log n) time, which means you cannot afford to look at every element.

Function

search(nums: integer-array, target: integer) → integer

numsinteger-array: the sorted list of distinct integers
targetinteger: the value to look for
Returnsinteger: the index of target in nums, or -1 if it is missing

Constraints

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
nums is sorted in strictly increasing order, so every value appears once.

Examples

Input: nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
Output: 4
Explanation: nums[4] is 9. The search looks at index 3 (value 4, too small), then index 5 (value 15, too big), then index 4, where it finds 9.

Input: nums = [1, 3, 5, 8, 13, 21]target = 10
Output: -1
Explanation: 10 would sit between 8 and 13, and neither is 10, so it is not in the list. The search range shrinks until lo passes hi, and the function returns -1.

+15 hidden tests on Submit

Follow-up

If nums could repeat values, how would you return the first index of target, still in O(log n)?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Reading the elements one by one finds target, but it ignores the one fact that makes the problem interesting: the list is sorted. A single comparison with the middle element tells you which half can still hold target, so you can discard half of the candidates on every step. A list of 10^4 elements then needs at most 14 comparisons instead of 10000.

Scan from left to right

Intuition

Check every index in order and return the first one whose value equals target. If the loop ends without a match, target is not in the list, so return -1. Every element is compared once, which makes the answer correct for any list, sorted or not.

That generality is the problem. A list of 10^4 elements costs up to 10000 comparisons, and the work grows in step with n. The scan never uses the fact that nums is sorted, so it misses the O(log n) bound the task asks for. You could stop early once a value passes target, but in the worst case you still read the whole list.

Algorithm

For each index i from 0 to n-1, compare nums[i] with target.
If they are equal, return i.
After the loop, return -1.

def search(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

Binary search with two indexes

Intuition

Keep two indexes, lo and hi, with one promise: if target is in the list, its index lies between lo and hi, inclusive. At the start that range is the whole list, 0 to n-1. Look at the middle index mid. If nums[mid] equals target, you are done. If it is smaller, then because the list is sorted every element up to mid is smaller too, so move lo to mid + 1. If it is larger, move hi to mid - 1. The promise still holds after either move.

Trace the first example, [-7, -2, 0, 4, 9, 15, 23] with target = 9. The range 0 to 6 has middle 3, value 4, too small, so the range becomes 4 to 6. Its middle 5 holds 15, too big, so the range becomes 4 to 4. Index 4 holds 9: return 4.

If target is missing, the range keeps shrinking until lo passes hi. The range is then empty, the promise says target is nowhere, and you return -1. Each step halves the range, so the loop runs at most about log2(n) + 1 times: 14 steps for 10^4 elements. Two indexes are all the extra memory you need.

Algorithm

Set lo = 0 and hi = n-1.
While lo ≤ hi, compute mid = lo + (hi - lo) / 2.
If nums[mid] equals target, return mid.
If nums[mid] < target, set lo = mid + 1; otherwise set hi = mid - 1.
When the loop ends, return -1.

def search(nums, target):
    lo, hi = 0, len(nums) - 1  # target, if present, sits in nums[lo..hi]
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1  # nums[mid] and everything left of it is too small
        else:
            hi = mid - 1  # nums[mid] and everything right of it is too big
    return -1

Pitfalls and edge cases

Binary search is short, and almost every bug is an off-by-one at the edges of the range.

Looping on lo < hi while hi starts at the last index. The loop stops while one candidate is still unchecked, so nums = [5] with target = 5 returns -1. With an inclusive range, loop while lo ≤ hi.
Moving to lo = mid or hi = mid with an inclusive range. When lo and hi are neighbours, mid equals lo and the range never shrinks: an endless loop. You already checked nums[mid], so step past it with mid + 1 or mid - 1.
Computing (lo + hi) / 2 in a fixed-width integer. The sum overflows once the indexes pass about 10^9. The limits here are far below that, but lo + (hi - lo) / 2 is the safe habit.
Returning lo when target is missing. After the loop lo is the insertion point, which is a valid index, not -1.
Forgetting the shift in Lua and R. Their lists start at 1, so the index you return is the position minus 1.

Frequently asked questions4

What is the time complexity of binary search?

O(log n). Every comparison halves the range that can still hold the target, so after k steps at most n / 2^k candidates remain. A list of 10^4 elements needs at most 14 comparisons, and a list of 10^9 elements at most 30. The iterative version uses O(1) extra space.

Why does binary search need a sorted array?

The step that discards half the list relies on order. When nums[mid] < target, sorting guarantees that every element left of mid is also smaller than target, so none of them can match. In an unsorted list that comparison says nothing about the other elements, and you have to check them all.

Should binary search be iterative or recursive?

Both are correct and both run in O(log n) time. The recursive version calls itself on one half and uses O(log n) stack space; the iterative version moves lo and hi in a loop and uses O(1). Interviewers usually expect the loop, and it avoids any recursion limit.

How do you avoid overflow when computing the middle index?

Write mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2. Both give the same index, but the second form adds two indexes first, and in a 32-bit integer that sum overflows once the indexes pass about 1.07 × 10^9. Python and Ruby have unbounded integers, so there the short form is safe.

Python

def search(nums, target):
    # Write code here

Test cases

Case 1

Case 2

Input

nums = [-7, -2, 0, 4, 9, 15, 23]
target = 9

Expected