# Search in Rotated Sorted Array – Leetcode Solution

In this post, we are going to solve the 33. Search in Rotated Sorted Array problem of Leetcode. This problem 33. Search in Rotated Sorted Array is a Leetcode medium level problem. Let’s see the code, 33. Search in Rotated Sorted Array – Leetcode Solution.

Contents

## Problem

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, nums, …, nums[k-1]`. 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 = , 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`

Now, let’s see the code of 33. Search in Rotated Sorted Array – Leetcode Solution.

# Search in Rotated Sorted Array – Leetcode Solution

### 33. Search in Rotated Sorted Array – Solution in Java

```class Solution {
public int search(int[] nums, int target) {

int s = 0;
int e = nums.length-1;

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

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

return -1;
}
}```

### 33. Search in Rotated Sorted Array – Solution in 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)>>1;
if(target==nums[mid])return mid;
else if(nums[mid]<=nums[e])
{if(target>=nums[mid] and target<=nums[e])
s=mid+1;
else e = mid-1;
}
else{
if(target>=nums[s] and target<=nums[mid])
e = mid-1;
else s = mid+1;
}
}
return -1;
}
};```

### 33. Search in Rotated Sorted Array– Solution in Python

```class Solution:

def search(self, nums, target):
if not nums:
return -1

low, high = 0, len(nums) - 1

while low <= high:
mid = (low + high) / 2
if target == nums[mid]:
return mid

if nums[low] <= nums[mid]:
if nums[low] <= target <= nums[mid]:
high = mid - 1
else:
low = mid + 1
else:
if nums[mid] <= target <= nums[high]:
low = mid + 1
else:
high = mid - 1

return -1```

Note: This problem 33. Search in Rotated Sorted Array is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.