Skip to content

704. Binary SearchΒΆ

Problem Link

Using the general template,

  • The search space is \([0,len(nums))\), so we initialize \(left = 0\) and \(right = len(nums)\).
  • The condition is to find the minimal index \(k\) such that \(nums[k] >= target\).
  • If the target exists in the array, the minimal value satisfying the condition will be target itself, and its index will be stored in left.
Runtime Complexity

Time: \(O(logn)\), search space is reduced by half in each iteration

Space: \(O(1)\), constant space from variables.

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

        return l if l < len(nums) and nums[l] == target else -1

func search(nums []int, target int) int {
    left, right := 0, len(nums)
    var mid int
    for left < right {
        mid = left + (right-left)/2
        if nums[mid] >= target {
            right = mid
        } else {
            left = mid + 1
        }
    }
    if left < len(nums) && nums[left] == target {
        return left
    }
    return -1
}