<jupyter_start><jupyter_text>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).Example 1:    Input: nums = [4,5,6,7,0,1,2], target = 0    Output: 4Example 2:    Input: nums = [4,5,6,7,0,1,2], target = 3    Output: -1<jupyter_code>class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        
        i, j = 0, len(nums) - 1
        
        while i <= j:
            mid = (i + j) // 2
            if nums[mid] == target:
                return mid
            
            if nums[i] <= nums[mid]:
                if nums[i] <= target <= nums[mid]:
                    j = mid - 1
                else:
                    i = mid + 1
            else:
                if nums[mid] <= target <= nums[j]:
                    i = mid + 1
                else:
                    j = mid - 1
        return -1

# test
nums = [4,5,6,7,0,1,2]
target = 0            
Solution().search(nums, target)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12428160919540229, 'fraction_numerical': 0.03735632183908046, 'mean_word_length': 1.570110701107011, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '510403', 'license': 'MIT', 'n_tokens_mistral': 478, 'n_tokens_neox': 447, 'n_words': 143, 'path': 'DSA/arrays/searchInRotatedArray.ipynb', 'repo_name': 'lance-lh/Data-Structures-and-Algorithms', 'size': '1392'}