{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Binary Search – Solution & Complexity

Interview solutions
/
Binary Search
Quick practice for Binary Search: 3 reasoning beats, no typing

Solution Walkthrough

  1. Step 1: Understand the Sorted Input

    • The array is sorted in ascending order.
    • You need return the index of target, or -1 if it is missing.
    • The requested O(log n) time means we should repeatedly discard half of the search range.

  2. Step 2: Why Linear Search Is Not Enough

    • Checking each element from left to right is simple and correct.
    • However, it can inspect every value in the worst case.
    • That makes it O(n), which does not meet the requirement.
    def search(nums: list[int], target: int) -> int:
    for i, value in enumerate(nums):
        if value == target:
            return i
    return -1

  3. Step 3: Use the Middle Element

    • Binary search keeps two pointers: left and right.
    • Look at the middle index between them.
    • If the middle value is too small, search the right half; if it is too large, search the left half.

  4. Step 4: Update the Search Bounds

    • When nums[mid] < target, all values at mid and left of it are too small, so move left to mid + 1.
    • When nums[mid] > target, all values at mid and right of it are too large, so move right to mid - 1.
    • Stop when the bounds cross.
    def search(nums: list[int], target: int) -> int:
    left = 0
    right = len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

  5. Step 5: Final Solution and Complexity

    • The equality check returns immediately when the target is found.
    • Each loop removes about half of the remaining values.
    • Time complexity is O(log n), and space complexity is O(1).
    def search(nums: list[int], target: int) -> int:
    left = 0
    right = len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1
Learn the Binary Search pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Binary Search online (run code in the browser)Find Minimum in Rotated Sorted Array solution (medium)Koko Eating Bananas solution (medium)Longest Increasing Subsequence solution (hard)Median of Two Sorted Arrays solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?