# 在排序的旋转数组中搜索

## 使用案列

```Input  : arr[] = {7,8,9,10,1,2,3,5,6};
key = 2
Output : Found at index 5

Input  : arr[] = {7,8,9,10,1,2,3,5,6};
key = 30

Input : arr[] = {4,8,16,1,2}
key = 2
Output : Found at index 4```

## 排序旋转数组中的搜索算法

1. 我们首先找到数据透视元素，数据透视元素是排序后的旋转数组中的两个数组元素，其两个邻居（数组中）均小于它。 基本上，枢轴是数组中最大的元素。 ivotSearch（）返回数据透视表的索引。
2. 找到枢轴后，我们将根据要搜索的元素的值执行二进制搜索范围[0，p]或范围[p，n-1]。

p =枢轴索引

n =数组的大小

```arr[] = {7,8,9,10,1,2,3,5,6}
Element to Search = 2
1.find out pivot p and divide the array into two subarrays range[lo,p] and range[p,hi]
2.perform binary search in one of the subarrays.
a. if key >= arr[0], call binary search in range[lo,p].
b. else call binary search in range[p,hi]
3.if key is found in selected sub-array then return it's index
else return -1.

lo(index number of first array element) = 0
hi(index number of last array element) = n-1
p = index of pivot
n = size of the array```

## 实施

### C ++程序

```#include <bits/stdc++.h>
using namespace std;

// Standard Binary Search function
int binarySearch(int arr[],int lo,int hi,int key)
{
if (lo <= hi)
{
int mid = (lo+hi)/2; /*low + (high - low)/2;*/

if (key == arr[mid])
return mid;

if (key > arr[mid])
return binarySearch(arr,mid+1,hi,key);

else
return binarySearch(arr,lo,mid-1,key);
}

return -1;  // low > high
}

/* Function to get pivot. For sorted rotated array 7,9,11,12,1,3 it returns 3 (index of 12) */
int pivotSearch(int arr[],int lo,int hi)
{
// base cases
if (hi < lo)
return -1;      // if array is not rotated at all
if (hi == lo)
return lo;

int mid = (lo+hi)/2; /*lo + (hi-lo)/2;*/

// pivot is greater than array element to it's right
if (mid < hi && arr[mid] > arr[mid+1])
return mid;
// pivot is greater than array element to it's left
if (mid > lo && arr[mid] < arr[mid-1])
return (mid-1);

if (arr[lo] >= arr[mid])
return pivotSearch(arr,lo,mid-1);   // pivot lies in left half
else
return pivotSearch(arr,mid+1,hi);   // pivot lies in right half

}

int pivotedBinarySearch(int arr[],int n,int key)
{
int pivot = pivotSearch(arr,0,n-1); // obtain the pivot index

// If no pivot is found,then array is not rotated at all
// in this case we perform a simple binary search as array is sorted (but not rotated)
if (pivot == -1)
return binarySearch(arr,0,n-1,key);

// If we found a pivot, then first compare with pivot value
if (arr[pivot] == key)
return pivot;

// else perform binary search in two subarrays around pivot

// if element to be searched is greater than first (0-index) array element
// then searched element lies between indices - 0 and pivot
if (arr[0] <= key)
return binarySearch(arr,0,pivot-1,key);
// else it lies between indices - pivot and n-1
else
return binarySearch(arr,pivot+1,n-1,key);
}

/* Main program to implement above functions */
int main()
{
// element to be searched = 3
int arr[] = {7,8,9,10,1,2,3,5,6};
int n = sizeof(arr)/sizeof(arr[0]);
int search = 2;

cout << "Index of "<<search<<" : "<<pivotedBinarySearch(arr,n,search);

return 0;
}
```
`Index of 2 : 5`

### Java程序

```class sortedRotatedSearch
{
// Standard Binary Search function
static int binarySearch(int arr[],int lo,int hi,int key)
{
if (lo <= hi)
{
int mid = (lo+hi)/2; /*low + (high - low)/2;*/

if (key == arr[mid])
return mid;

if (key > arr[mid])
return binarySearch(arr,mid+1,hi,key);

else
return binarySearch(arr,lo,mid-1,key);
}

return -1;  // low > high
}

/* Function to get pivot. For sorted rotated array 7,9,11,12,1,3 it returns 3 (index of 12) */
static int pivotSearch(int arr[],int lo,int hi)
{
// base cases
if (hi < lo)
return -1;      // if array is not rotated at all
if (hi == lo)
return lo;

int mid = (lo+hi)/2; /*lo + (hi-lo)/2;*/

// pivot is greater than array element to it's right
if (mid < hi && arr[mid] > arr[mid+1])
return mid;
// pivot is greater than array element to it's left
if (mid > lo && arr[mid] < arr[mid-1])
return (mid-1);

if (arr[lo] >= arr[mid])
return pivotSearch(arr,lo,mid-1);   // pivot lies in left half
else
return pivotSearch(arr,mid+1,hi);   // pivot lies in right half

}

// function to search an element in sorted-rotated array
static int pivotedBinarySearch(int arr[],int n,int key)
{
int pivot = pivotSearch(arr,0,n-1); // obtain the pivot index

// If no pivot is found,then array is not rotated at all
// in this case we perform a simple binary search as array is sorted (but not rotated)
if (pivot == -1)
return binarySearch(arr,0,n-1,key);

// If we found a pivot, then first compare with pivot value
if (arr[pivot] == key)
return pivot;

// else perform binary search in two subarrays around pivot

// if element to be searched is greater than first (0-index) array element
// then searched element lies between indices - 0 and pivot
if (arr[0] <= key)
return binarySearch(arr,0,pivot-1,key);
// else it lies between indices - pivot and n-1
else
return binarySearch(arr,pivot+1,n-1,key);
}

// main function to implement above function
public static void main(String args[])
{
// Let us search 3 in below array
int arr[] = {7,8,9,10,1,2,3,5,6};
int n = arr.length;
int key = 2;
System.out.println("Index of "+key+" is : "+ pivotedBinarySearch(arr,n,key));
}
}```
```Index of 2 is : 5
```

## 用于排序旋转阵列的改进的搜索解决方案/算法

```1. find mid point of the range [lo,hi] as mid = (lo+hi)/2
2. if arr[mid] == key : return mid.
3. else if range [lo,mid-1] is sorted
a. if arr[lo] <= key <= arr[mid],search for key in range[lo,mid].
b. else recur for range [mid+1,hi].
4. else range[mid+1,hi] must be sorted
a. if arr[mid+1] <= search <= arr[hi],search for key range[mid+1,hi].
b. else recur for range [lo,mid].```

## 实施

### C ++程序

```#include <bits/stdc++.h>
using namespace std;

// Returns index of searched element 'key' in arr[lo,hi] if key is present
// or else returns -1
int find(int arr[],int lo,int hi,int key)
{
if (lo > hi)
return -1;

int mid = (lo+hi)/2;

if (arr[mid] == key)
return mid;

// if arr[lo,mid-1] is sorted
if (arr[lo] <= arr[mid])
{
if (key >= arr[lo] && key <= arr[mid])
return find(arr,lo,mid-1,key);      // check if key lies in range[lo,mid-1]

else
return find(arr,mid+1,hi,key);      // else recur for range[mid+1,hi]
}
// else arr[mid+1,hi] must be sorted
else
{
if (key >= arr[mid] && key <= arr[hi])
return find(arr,mid+1,hi,key);         // check if key lies in range[mid+1,hi]

else
return find(arr,lo,mid-1,key);         // else recur for range[lo,mid-1]
}
}

// Main Program to implement above functions
int main()
{
int arr[] = {7,8,9,10,1,2,3,5,6};
int n = sizeof(arr)/sizeof(arr[0]);
int key = 2;
int i = find(arr, 0, n-1, key);

i != -1 ? cout<<"Index of "<<key<<" : "<<i<<endl : cout<<"Element Not found";
}
```
`Index of 2 : 5`

### Java程序

```class sortedRotatedSearch
{
// Returns index of searched element 'key' in arr[lo,hi] if key is present
// or else returns -1
static int find(int arr[],int lo,int hi,int key)
{
if (lo > hi)
return -1;

int mid = (lo+hi)/2;

if (arr[mid] == key)
return mid;

// if arr[lo,mid-1] is sorted
if (arr[lo] <= arr[mid])
{
if (key >= arr[lo] && key <= arr[mid])
return find(arr,lo,mid-1,key);      // check if key lies in range[lo,mid-1]

else
return find(arr,mid+1,hi,key);      // else recur for range[mid+1,hi]
}
// else arr[mid+1,hi] must be sorted
else
{
if (key >= arr[mid] && key <= arr[hi])
return find(arr,mid+1,hi,key);         // check if key lies in range[mid+1,hi]

else
return find(arr,lo,mid-1,key);         // else recur for range[lo,mid-1]
}
}

// Main Program to implement above functions
public static void main(String args[])
{
int arr[] = {7,8,9,10,1,2,3,5,6};
int n = arr.length;
int key = 2;
int i = find(arr,0,n-1,key);

if (i != -1)
System.out.println("Index of "+key+" : "+i);
else
}
}
```
`Index of 2 : 5`

## 复杂度分析

1. 时间复杂度T（n）= O（logn）
2. 空间复杂度A（n）= O（1）

• 当排序后的旋转数组包含重复元素时，以上算法不适用。