704. Binary Search

[chengchengxu15]

https://leetcode.com/problems/binary-search/

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

[chengchengxu15]

time complexity: O(logn) space complexity: O(logn)

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