{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Binary Search – Solution & Complexity

Interview solutions
/
Binary Search

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. 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. 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. 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. 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

FAQ

See also:

Practice Binary Search online (run code in the browser)Longest Increasing Subsequence solution (hard)Median of Two Sorted Arrays solution (hard)Search Insert Position solution (easy)Best Time to Buy and Sell Stock solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?