Binary search

Given an ordered (ascending) integer array nums with n elements and a target value, write a function to search for target in NUMs, returning a subscript if the target value exists, and -1 otherwise.

Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 appears in nums with subscript 4

Example 2: Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Description: 2 does not exist in NUMs so -1 is returned

Their thinking

Depending on the problem and the ordered array, just use dichotomy. Easy problem

The sample code

def search(self, nums: List[int], target: int) - >int:
        if not nums:
            return -1

        l, r = 0.len(nums) - 1

        while l <= r:
            mid = (l + r) // 2
            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] < target:
                l = mid + 1
            else:
                return mid
        return -1
Copy the code