Search in Rotated Sorted Array[M,Array,Binary Search]

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

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

1. C

#C
#Binary Search
int search(int* nums, int numsSize, int target) {
    int s = 0;
    int e = numsSize-1;

    while(s<=e){
        int mid = s+(e-s)/2;
        if(nums[mid] == target) return mid;

        else if(nums[s] <= nums[mid]){
            if( nums[mid]>= target && nums[s] <= target){
                e = mid-1;
            }else{
                s = mid+1;
            }
        }
        
        else{
            if( nums[mid] <= target && nums[e] >= target ){
                s = mid+1;
            }else{
                e = mid-1;
            }

        }
    }
        return -1;
}

 

 

2. C++

C와 유사하다.

# C++
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int s = 0;
        int e = nums.size()-1;

        while(s<=e){
            int mid = s+(e-s)/2;

            if(nums[mid]==target) return mid;
            else if(nums[s] <= nums[mid]){
                if(nums[mid] >= target && nums[s] <= target){
                    e = mid-1;
                }else{
                    s = mid+1;
                    }
            }
            else{
                if(nums[mid] <= target && nums[e] >= target){
                    s = mid+1;
                }else{
                    e = mid-1;
                    }
            }
            
        }
        return -1;
    }
};

 

 

3. Python

걍 재미삼아 해본 코드

이렇게 해도 되는디..?

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        try:
            idx = nums.index(target)
            return idx
        except: return -1