Binary Search

Q: What is the time complexity of binary search?

O(log n) time. Every comparison halves the range that can still hold the target, so a list of 10^9 elements needs at most 30 comparisons. The iterative version uses O(1) extra space.

Q: Should binary search be iterative or recursive?

Both are correct and both run in O(log n) time. The recursive version uses O(log n) stack space; the loop that moves lo and hi uses O(1) . Interviewers usually expect the loop.

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 in a 32-bit integer the sum lo + hi overflows once the indexes pass about 1.07 × 10^9 . Python and Ruby have unbounded integers, so the short form is safe there.

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.

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

The list is sorted, so one comparison with the middle element tells you which half can still hold target. Discarding half the candidates on every step means a list of 10^4 elements needs at most 14 comparisons instead of 10,000.

Scan from left to right

Intuition

Compare every element with target in order and return the first match, or -1 after the loop. It is correct for any list, sorted or not.

It never uses the order, so a list of 10^4 elements costs up to 10,000 comparisons: O(n), not the O(log n) the task asks for.

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 them, inclusive. When nums[mid] is smaller than target, every element up to mid is smaller too, because the list is sorted, so lo can move past mid. A larger nums[mid] moves hi below mid for the same reason. The promise survives every move.

When target is missing, the range shrinks until lo passes hi. The range is then empty, so the promise says target is nowhere. Each step halves the range, so the loop runs at most about log2(n) + 1 times, with two indexes of extra memory.

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

Looping on lo < hi while hi starts at the last index. The loop stops with one candidate unchecked, so nums = [5] with target = 5 returns -1.
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.
Returning lo when target is missing. After the loop lo is the insertion point, 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 questions3

What is the time complexity of binary search?

O(log n) time. Every comparison halves the range that can still hold the target, so a list of 10^9 elements needs at most 30 comparisons. The iterative version uses O(1) extra space.

Should binary search be iterative or recursive?

Both are correct and both run in O(log n) time. The recursive version uses O(log n) stack space; the loop that moves lo and hi uses O(1). Interviewers usually expect the loop.

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 in a 32-bit integer the sum lo + hi overflows once the indexes pass about 1.07 × 10^9. Python and Ruby have unbounded integers, so the short form is safe there.

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

Test #1

Test #2

Arguments

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

Expected Output