# Leetcode-Search Rotated Array

## 题目描述

Suppose a sorted array 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`).

You are given a target value to search. If found in the array return its `index`, otherwise return `-1`.

You may assume `no duplicate exists` in the array.

## 思路

• 1.A[l] < A[r]，说明A[l] < A[l + 1] < A[l + 2] < … < A[r]是一个部分有序数组，可以直接采用二分查询；
• 2.A[l] > A[r]，说明存在一个k，使得A[l]到A[k]，A[k+1]到A[r]为两个有序数组，此时我们还是用二分处理：

## AC代码

``````#include <iostream>

using namespace std;

int search(int A[], int n, int target)
{
int left = 0;
int right = n - 1;
while(left < right)
{
int mid = left + (right - left) / 2;  //bin sort
if(A[mid] >= A[left] ) //if left side sorted
{
if(A[left] <= target && target <= A[mid])
right = mid;
else
left = mid + 1;
}
else //if right side sorted
{
if(A[mid] <= target && target <= A[right])
left = mid;
else
right = mid - 1;
}
}
if(right >= 0 && right < n && A[right] == target)
return right;
else
return -1;
}

int main()
{
int n;
cin>>n;
int A[n];
for(int i = 0; i < n; i++)
cin>>A[i];
int target;
cin>>target;

cout<<search(A, n, target)<<endl;
return 0;
}
``````