33.-search-in-rotated-sorted-array.md

33. Search in Rotated Sorted Array

{% tabs %} {% tab title="CPP" %}

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int ans = -1;
        if (nums.size()==0) return ans;
        int left = 0;
        int right = nums.size() - 1;
        while (left <= right) {
            int mid = (right - left )/2 + left;
            if (nums[mid] == target){
                return mid ;
            }
            
            else if (nums[mid] > nums[left]) {
                if (nums[left] <= target && target < nums[mid]){
                    right = mid ;
                } else {
                    left = mid + 1;
                }
            }
            else {
                if ((nums[mid] < target && target <= nums[right])){
                    left = mid + 1;
                    
                } else {
                    right = mid;
                }
            }
        }
        return nums[left] == target ? left : ans;
    }
};

{% endtab %}

{% tab title="Python" %}

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        
        
        ans = -1
        if not nums:
            return ans 
        l = 0
        r = len(nums)-1
        while l < r:
            
            mid = (l+r)//2
            if nums[mid] == target:
                return mid
                
            # left ordered
            elif nums[l] < nums[mid]:
                if nums[l] <= target < nums[mid]:
                    r = mid
                else:
                    l = mid + 1
                
            else:
                if nums[mid+1] <= target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid
                
        
        return l if nums[l] == target else ans

{% endtab %} {% endtabs %}