# Search In Rotated Sorted Array Problem Solution

Search In Rotated Sorted Array 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[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 :

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

Output: 4

## Problem Solution In Python

``````class Solution:
def search(self, nums, target):
def search(nums, l, r):
m = (l + r) // 2
if nums[m] == target:
return m
if l == r:
return -1
if nums[l] < nums[m]:
if target >= nums[l] and target < nums[m]:
return search(nums, l, m - 1)
else:
return search(nums, m + 1, r)
elif r - m == 1:
if nums[r] == target:
return r
else:
return search(nums, l, m)
elif nums[m + 1] < nums[r]:
if target >= nums[m + 1] and target <= nums[r]:
return search(nums, m + 1, r)
else:
return search(nums, l, m - 1)
return -1

return -1 if not nums else search(nums, 0, len(nums) - 1)
``````

## Problem Solution In Java

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

if(nums.length == 1){
return nums[0] == target ? 0 : -1;
}
int i=0;
int j = nums.length-1;
while(i<j){
if(nums[i] == target){
return i;
}
else if(nums[j] == target){
return j;
}
else if(target > nums[i]){
i++;
}
else{
j--;
}
}
return -1;
}
}
``````

## Problem Solution In C++

``````class Solution {
public:
int b_Search(vector<int>& nums, int target, int low, int high) {
while(low <= high) {
int mid = low + (high - low) / 2;
if(nums[mid] == target) return mid;
else if(nums[mid] > target) high = mid - 1;
else low = mid + 1;
}
return -1;
}

int search(vector<int>& nums, int target) {
int i = 0;
for(; i < nums.size() - 1; i++) {
if(nums[i] > nums[i + 1]) break;
}
int ans = b_Search(nums, target, 0, i);
if(ans != -1 || i == nums.size() - 1) return ans;
ans = b_Search(nums, target, i+1, nums.size() - 1);
return ans;
}
};
``````

## Problem Solution In C

``````int search(int* nums, int numsSize, int target){

int i = 0;
for(i = 0;i<numsSize;i++)
{
if((nums[i] == target) )
return i;
if((nums[numsSize - i-1] == target ))
return (numsSize-i-1);
}

return -1;
}
``````