#05EasyAlgorithms · 68% acceptance

Search the Sorted Threshold

Binary SearchArray

Given a sorted array `nums` and a `target`, return the index of `target`, or -1 if it is absent.

Halving the search space each step is the same instinct as a titration — narrow in until you bracket the answer.

Examples

Input: nums = [-1,0,3,5,9,12], target = 9

Output: 4

Input: nums = [-1,0,3,5,9,12], target = 2

Output: -1

Constraints

·1 ≤ nums.length ≤ 10^4
·nums is sorted in ascending order.

Hints

solution.pyPython 3

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

Test console

// hit Run to execute the sample tests

// Interactive editor preview. Live code execution arrives with your early-access cohort.