Simply Python Binary Search O(NlogN) Solution


  • 0
    J

    Modified binary search, search left under these conditions:
    target < mid <= end
    start= < target < mid
    mid <= end < target

    class Solution(object):
        def search(self, nums, target):
            """
            :type nums: List[int]
            :type target: int
            :rtype: int
            """
            if not nums:
                return -1
            return self.search_helper(nums, target, 0, len(nums)-1)
        
        def search_helper(self, nums, target, start, end):
            if start > end:
                return -1
            mid = (start + end)//2
            if nums[mid] == target:
                return mid
            
            if target < nums[mid] <= nums[end] or nums[start] <= target < nums[mid] or target > nums[end]>= nums[mid]:
                return self.search_helper(nums, target, start, mid-1)
    

Log in to reply
 

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