# Blogs Hub

### by Sumit Chourasia | Oct 24, 2020 | Category :coding | Tags : algorithmarraydata-structureleetcodemedium #### Search in Rotated Sorted Array - Array - Medium - LeetCode

You are given an integer array nums sorted in ascending order, and an integer target.

Suppose that nums 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]).

If target is found in the array return its index, otherwise, return -1.

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
-10^4 <= nums[i] <= 10^4
All values of nums are unique.
nums is guranteed to be rotated at some pivot.
-10^4 <= target <= 10^4

``````public class Solution {
public int Search(int[] nums, int target) {
int low = 0;
int high = nums.Length-1;
int len = nums.Length;
while(low<high){
int mid = low+(high-low)/2;
if(nums[mid]>nums[high]){
low=mid+1;
}
else{
high=mid;
}
}

int rotation = low;

low=0;
high = nums.Length-1;
while(low<=high){
int mid = low+(high-low)/2;
int actualMid = (mid + rotation)%len;
if(nums[actualMid]==target){
return actualMid;
}
else if(nums[actualMid]<target){
low=mid+1;
}
else{
high=mid-1;
}
}

return -1;
}

}``````

Time Complexity: O(logn)

Space Complexity: O(1)