search_in_rotated_sorted_array.py

# Search in Rotated Sorted Array
# https://leetcode.com/problems/search-in-rotated-sorted-array/

# Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
# (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

# You are given a target value to search. If found in the array return its index, otherwise return -1.

# You may assume no duplicate exists in the array.
# Your algorithm's runtime complexity must be in the order of O(log n).

# My solution:
# Runtime: 20 ms, faster than 96.24% of Python online submissions for Search in Rotated Sorted Array.
# Memory Usage: 10.9 MB, less than 46.81% of Python online submissions for Search in Rotated Sorted Array.

class Solution(object):
    def search(self, nums, target, start_idx=None, end_idx=None):
        if not nums:
            return -1

        if start_idx is None and end_idx is None:
            start_idx = 0
            end_idx = len(nums)

        middle_idx = (end_idx + start_idx) / 2
        left_half = nums[start_idx:middle_idx]
        right_half = nums[middle_idx:end_idx]
    
        if nums[middle_idx] == target:
            return middle_idx
    
        if len(left_half) == 1:
            if left_half[0] == target:
                return middle_idx - 1
        
        if len(right_half) == 1:
            if right_half[0] == target:
                return middle_idx + 1
    
        if (len(left_half) <= 1) and (len(right_half) <= 1):
            return -1
        
        left_half_contains_target = self._does_left_half_contain_target(target, left_half, right_half)

        new_start_idx, new_end_idx = self._get_new_boundaries(start_idx, end_idx, middle_idx, left_half_contains_target)

        return self.search(nums, target, start_idx=new_start_idx, end_idx=new_end_idx)

    def _does_left_half_contain_target(self, target, left_half, right_half):
        target_in_left = False
        if not left_half:
            return False

        if len(left_half) == 1:
            if left_half[0] == target:
                return True
        elif (left_half[0] > left_half[-1]):
            # is target within bounds of ordered right side?
            target_in_left = not (right_half[0] <= target <= right_half[-1])
        else:
            # is target within bounds of ordered left side?
            target_in_left = (left_half[0] <= target <= left_half[-1])    

        return True if target_in_left else False

    def _get_new_boundaries(self, start_idx, end_idx, middle_idx, left_half_contains_target):
        if left_half_contains_target:
            end_idx = middle_idx
        else:
            start_idx = middle_idx

        return start_idx, end_idx