Python binary search with recursion


  • 0
    L

    The key is to decide the largest element is in which half of the current range for each loop. My solution is 1) For those cases where we can know which half the largest element is located, reduce the range by changing start or end position. 2) For those cases like [1,1,1,2,1], where elements in the start, middle and end positions are equal, we recursively search for both sides. Best case O(logN) worst caseO(N)

    class Solution:
        def _search(self, nums, target, start, end):
            while start <= end:
                mid = (start + end) / 2
                if nums[mid] == target:
                    return True
                temp_start = start
                temp_end = end
                if nums[mid] > nums[start] or nums[mid] > nums[end]:
                    if nums[start] <= target <= nums[mid]:
                        end = mid - 1
                    else:
                        start = mid + 1
                elif nums[mid] < nums[start] or nums[mid] < nums[end]:
                    if nums[mid] <= target <= nums[end]:
                        start = mid + 1
                    else:
                        end = mid - 1
                if self._search(nums, target, start + 1, mid- 1):
                    return True
                if self._search(nums, target, mid + 1, end - 1):
                    return True
                if temp_start == start and temp_end == end:
                    return False
            return False
    
        def search(self, nums, target):
            if not nums:
                return False
            start, end = 0, len(nums) - 1
            return self._search(nums, target, start, end)

Log in to reply
 

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