**source:**https://leetcode.com/problems/search-in-rotated-sorted-array**C/C++**

**Solution to LeetCode**problem

**33**.

**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.

## Examples

**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`

`-10`

^{4}<= nums[i] <= 10^{4}- All values of
`nums`

are**unique**. `nums`

is an ascending array that is possibly rotated.`-10`

^{4}<= target <= 10^{4}

## Solution

The logic is as follows:

- Binary search splits the array in two.
- If the array is rotated, one part will be sorted, and the other not.
- First we identify the sorted half (the sorted part has the value at the lower index
`<=`

that the value at the middle index).- If the
`target`

is in the sorted part, then we update our indexes to perform the next binary search in that part. - If not, then it means the
`target`

is in the unsorted part, so we update indexes to perform next search there.

- If the

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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