EasyArrayBinary SearchDivide and Conquer

Binary Search

2 approaches, code in every language

You are given an array of integers arr that is arranged in strictly increasing order, together with a value target. Report the 0-based index at which target appears. When the value does not occur anywhere in the array, return -1 instead.

Because the input is already sorted, you should not scan every element. Aim for a logarithmic-time solution that repeatedly narrows the region under consideration by comparing the target against the middle element and discarding the half that cannot contain it.

Example 1

Input: arr = [-2, 0, 3, 5, 9, 12], target = 9

Output: 4

The value 9 is stored at index 4, so that index is returned.

Example 2

Input: arr = [-2, 0, 3, 5, 9, 12], target = 2

Output: -1

No element equals 2, so the search reports -1.

Constraints

1 <= arr.length <= 10^4
-10^4 <= arr[i], target <= 10^4
arr is sorted in strictly increasing order with unique values

Recursive Halving

Compare the target with the middle element and recurse into the single half that could still hold it.

Loading animation…

Intuition

A sorted array lets us decide, from one comparison, which side of the midpoint the answer must lie on. If the middle value equals the target we are done; if it is smaller, everything to its left is too small, so we search the right side; otherwise we search the left side. Each recursive call shrinks the candidate window to half its size, which is why the number of steps grows only logarithmically with the length of the input.

Algorithm walkthrough

1Start with the whole array by calling the helper with lo = 0 and hi = length - 1.
2If lo ever exceeds hi the window is empty, meaning the target is absent, so return -1.
3Compute mid as the midpoint of lo and hi and inspect arr[mid].
4If arr[mid] equals the target return mid; if it is less than the target recurse on [mid + 1, hi]; otherwise recurse on [lo, mid - 1].
5The recursion unwinds with either a found index or -1 bubbling back to the caller.

Implementation

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def helper(lo: int, hi: int) -> int:
            if lo > hi:
                return -1
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                return helper(mid + 1, hi)
            return helper(lo, mid - 1)

        return helper(0, len(nums) - 1)

Time

O(log n)

Space

O(log n)

The recursion depth is logarithmic; an iterative version uses O(1) space.

Iterative Window

Maintain an explicit [lo, hi] window and shrink it in a loop instead of recursing.

Loading animation…

Intuition

The recursive halving pattern can be flattened into a single loop. We keep two pointers marking the inclusive bounds of the still-unexplored region and repeatedly test the midpoint. Rewriting the recursion as iteration removes the call-stack overhead while keeping the same logarithmic step count, so it is the version usually preferred in production.

Algorithm walkthrough

1Initialise lo to 0 and hi to the last index.
2While lo is not greater than hi, compute the midpoint mid.
3Return mid immediately when arr[mid] matches the target.
4Move lo to mid + 1 when the midpoint value is too small, or hi to mid - 1 when it is too large.
5If the loop finishes without a match, return -1.

Implementation

from typing import List


class Solution:
    def search(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                lo = mid + 1
            else:
                hi = mid - 1
        return -1

Time

O(log n)

Space

O(1)

Only two integer pointers are stored regardless of input size.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Recursion

After the pattern

Now solve one you haven't seen.

Survey Marker Lookup is our own problem on the technique behind Binary Search: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free

Binary Search

Problem description

Example 1

Example 2

Constraints

Create a free account to see the solution

Now solve one you haven't seen.