FresherFresher (0–1 yrs)CodingPythonAmazonMicrosoftTCS

Binary Search

Implement binary search to return the index of target in a sorted ascending array, or -1 if absent.

Answers use simple, clear English.

Time: O(log n)Space: O(1)

Quick interview answer

Maintain inclusive/exclusive bounds consistently. Mid = lo + (hi-lo)//2 to avoid overflow in fixed-width languages. Adjust lo/hi until empty range.

Detailed answer

Maintain inclusive/exclusive bounds consistently. Mid = lo + (hi-lo)//2 to avoid overflow in fixed-width languages. Adjust lo/hi until empty range. Off-by-one bugs dominate interviews — state your invariant aloud.

Full explanation

Off-by-one bugs dominate interviews — state your invariant aloud.

Real example & use case

Looking up a versioned config blob by monotonic deploy id.

Pros & cons

Pros: O(log n). Cons: only sorted data; duplicates need lower/upper bound variants.

Code example

def binary_search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Practice code · python (view only · no execution)

def binary_search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

#binary-search#basics