# Search Rotated Array

An array is sorted without duplicates. However, someone mysteriously shifted all the elements in this array (e.g. 1,2,3,4,5 -> 5,1,2,3,4). Implement a function to find an element in such array (return -1 if no such element).

## Solution

1. 待搜索元素落在有序的那一半(即大于最左元素且小于最右元素)。
2. 待搜索元素不在有序的那一半。

1. 通过中间元素将数组划分为两个半边
2. 通过比较切割后两半数组各自的头尾数据大小，确定哪一半是完全有序的
3. 判断待搜索元素落在哪个半边，减半搜索范围

## Code

``````int searchInRotatedArray(int[] arr, int target){
int len = arr.length;
return helper(arr, 0, len-1, target);
}

int helper(int[] arr, int low, int high, int target){
if (low > high) return -1;

int mid = high - (high - low) / 2;
if (arr[mid] == target)
return mid;

if (arr[low] <= arr[mid]){
// left part is sorted
if (target >= arr[low] && target <= arr[mid]){
return helper(arr, low, mid-1, target);
} else {
return helper(arr, mid+1, high, target);
}
} else {
// right part is sorted
if (target >= arr[mid] && target <= arr[high]){
return helper(arr, mid+1, high, target);
} else {
return helper(arr, low, mid-1, target);
}
}
}

``````