Easy

Binary Search

031

Given an ascending array of distinct integers nums and an integer target, return the index of target. Return -1 when target is not present.

EXAMPLES

Example 1

Input
{
  "nums": [
    -1,
    0,
    3,
    5,
    9,
    12
  ],
  "target": 9
}

Output
4

FUNCTION SHAPE

nums: intArraytarget: int→int

SOLUTION NOTE

Min template with post-processing check. If multiple occurrences exist: Min template → leftmost, Max template → rightmost.

Reveal reference solution +

pythonREFERENCE

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

TimeO(log n)

SpaceO(1)

Open on LeetCode ↗