# Search in Rotated Sorted Array

## Problem

### Description

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.

#### Example

For [4, 5, 1, 2, 3] and target=1, return 2.

For [4, 5, 1, 2, 3] and target=0, return -1.

O(logN) time

## 题解1 - 找到有序数组

### C++

/**
* 本代码fork自
* http://www.jiuzhang.com/solutions/search-in-rotated-sorted-array/
*/
class Solution {
/**
* param A : an integer ratated sorted array
* param target :  an integer to be searched
* return : an integer
*/
public:
int search(vector<int> &A, int target) {
if (A.empty()) {
return -1;
}

vector<int>::size_type start = 0;
vector<int>::size_type end = A.size() - 1;
vector<int>::size_type mid;

while (start + 1 < end) {
mid = start + (end - start) / 2;
if (target == A[mid]) {
return mid;
}
if (A[start] < A[mid]) {
// situation 1, numbers between start and mid are sorted
if (A[start] <= target && target < A[mid]) {
end = mid;
} else {
start = mid;
}
} else {
// situation 2, numbers between mid and end are sorted
if (A[mid] < target && target <= A[end]) {
start = mid;
} else {
end = mid;
}
}
}

if (A[start] == target) {
return start;
}
if (A[end] == target) {
return end;
}
return -1;
}
};


### Java

public class Solution {
/**
*@param A : an integer rotated sorted array
*@param target :  an integer to be searched
*return : an integer
*/
public int search(int[] A, int target) {
if (A == null || A.length == 0) return -1;

int lb = 0, ub = A.length - 1;
while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (A[mid] == target) return mid;

if (A[mid] > A[lb]) {
// case1: numbers between lb and mid are sorted
if (A[lb] <= target && target <= A[mid]) {
ub = mid;
} else {
lb = mid;
}
} else {
// case2: numbers between mid and ub are sorted
if (A[mid] <= target && target <= A[ub]) {
lb = mid;
} else {
ub = mid;
}
}
}

if (A[lb] == target) {
return lb;
} else if (A[ub] == target) {
return ub;
}
return -1;
}
}


### 源码分析

1. target == A[mid]，索引找到，直接返回
2. 寻找局部有序数组，分析A[mid]和两段有序的数组特点，由于旋转后前面有序数组最小值都比后面有序数组最大值大。故若A[start] < A[mid]成立，则start与mid间的元素必有序（要么是前一段有序数组，要么是后一段有序数组，还有可能是未旋转数组）。
3. 接着在有序数组A[start]~A[mid]间进行二分搜索，但能在A[start]~A[mid]间搜索的前提是A[start] <= target <= A[mid]
4. 接着在有序数组A[mid]~A[end]间进行二分搜索，注意前提条件。
5. 搜索完毕时索引若不是mid或者未满足while循环条件，则测试A[start]或者A[end]是否满足条件。
6. 最后若未找到满足条件的索引，则返回-1.

## 题解2 - 应用两次二分

### Java

public class Solution {
/**
*@param A : an integer rotated sorted array
*@param target :  an integer to be searched
*return : an integer
*/
public int search(int[] A, int target) {
if (A == null || A.length == 0) {
return -1;
}

int p = findBreakPoint(A);
if (target >= A[0]) {
// search in [lo, segPoint]
return binSearch(A, target, 0, p);
} else {
// search in [segPoint, hi]
return binSearch(A, target, p, A.length - 1);
}
}

private int findBreakPoint(int[] A) {
// A[index] < A[0], min[index]
int index;

int lo = 0, hi = A.length - 1, segValue = A[0];
while (lo + 1 < hi) {
int md = lo + (hi - lo)/2;
if (A[md] > segValue) {
lo = md;
} else {
hi = md;
}
}
index = A[lo] < segValue ? lo : hi;

return index;
}

private int binSearch(int[] A, int target, int lo, int hi) {
while (lo + 1 < hi) {
int md = lo + (hi - lo) / 2;
if (A[md] == target) {
lo = md;
} else if (A[md] < target) {
lo = md;
} else {
hi = md;
}
}

if (A[lo] == target) {
return lo;
}
if (A[hi] == target) {
return hi;
}
return -1;
}
}