What am I doing wrong in this question- Search in Rotated Sorted Array...?-CodePudding

Question:

There is an integer array nums sorted in ascending order (with distinct values).

Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k 1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

You must write an algorithm with O(log n) runtime complexity.

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

Constraints:

1 <= nums.length <= 5000
-104 <= nums[i] <= 104

All values of nums are unique. nums is an ascending array that is possibly rotated.

-104 <= target <= 104

My Code:

class Solution(object):
    def search(self, arr, x):
        l=0
        u=len(arr)-1
        m=0
    
        while(l<=u):
            m=(u l)//2

            if(arr[m]==x):
                return m
            elif(arr[m]<x):
                l=m 1  
            else:
                u=m-1

        return -1

CodePudding user response：

You can use binary-search but you need to consider that the array of the problem is not sorted (sorted but rotated) and you need to find the sorted part of the array on the left or right of middle.

class Solution:
    def search(self, arr, x):
        
        l=0
        u=len(arr)-1
        m=0
        
        while l<=u :
            m = l (u-l)//2 

            if arr[m] == x :
                return m
            
            elif arr[m] >= arr[l] :

                # sorted part is left-side of middle
                if x >= arr[l] and x < arr[m]: 
                    u = m-1
                
               # sorted part is right-side of middle
                else:                          
                    l = m 1
            else:

                # sorted part is right-side of middle
                if x <= arr[u] and x > arr[m]:
                    l = m 1                    
                
                # sorted part is left-side of middle
                else:
                    u = m-1                    
        return -1

Check:

>>> Solution().search([4,5,6,7,0,1,2], 0)
4

>>> Solution().search([4,5,6,7,0,1,2], 3)
-1

>>> Solution().search([1], 0)
-1

CodePudding user response：

Could you simply use the index command

nums = [4,5,6,7,0,1,2]
nums.index(5)
1

try: out = nums.index(200) 
except: out = -1
print(out)
-1