Python Quick 2-pass Binary Search (beating 98.95%)


  • 0
    M
    class Solution(object):
        def search(self, nums, target):
            if not nums:
                return -1
            l,r=0,len(nums)-1
            while l<=r:
                m=(l+r)/2
                if nums[m]<nums[0]:
                    r=m-1
                else:
                    l=m+1
    
            if nums[0]>target:
                r=len(nums)-1
            else:
                l=0
            
            while l<=r:
                m=(l+r)/2
                if nums[m]==target:
                    return m
                if nums[m]<target:
                    l=m+1
                else:
                    r=m-1
            return -1
    

    I also appreciate that there's a clever 1-pass solution. I haven't tried to implement it and I can't be very sure which is faster.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.