【题目】
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.
【分析】
循环递增数组有这么一个性质：以数组中间元素将循环递增数组划分为两部分，则一部分为一个严格递增数组，而另一部分为一个更小的循环递增数组。
当中间元素大于首元素时，前半部分为严格递增数组，后半部分为循环递增数组；当中间元素小于首元素时，前半部分为循环递增数组；后半部分为严格递增数组。
【代码】
/*********************************
* 日期：2014-01-15
* 作者：SJF0115
* 题号: 33.Search in Rotated Sorted Array
* 来源：http://oj.leetcode.com/problems/search-in-rotated-sorted-array/
* 结果：AC
* 来源：LeetCode
* 总结：
**********************************/
#include <iostream>
#include <stdio.h>
using namespace std;
class Solution {
public:
//二分查找
int search(int A[], int n, int target) {
int start = 0,end = n-1;
int mid;
while(start <= end){
mid = (start + end) / 2;
if(A[mid] == target){
return mid;
}
//中间元素大于最左边元素则左部分为有序数组
else if(A[mid] >= A[start]){
//目标位于左部分
if(target >= A[start] && target <= A[mid]){
end = mid - 1;
}
//目标位于右部分
else{
start = mid + 1;
}
}
//中间元素小于最右边元素则右部分为有序数组
else{
//目标位于右部分
if(target <= A[end] && target >= A[mid]){
start = mid + 1;
}
//目标位于左部分
else{
end = mid - 1;
}
}
}
return -1;
}
};
int main() {
int result;
Solution solution;
int A[] = {3,1};
result = solution.search(A,2,1);
printf("Result:%d\n",result);
return 0;
}
【分析二】
对于一个数组4,5,6,7,0,1,2 你首先找到那个转折点,就是大于下一个相邻数字的那个数字的下标,在这个数组就是数字7的下标3。
步骤：
1 找到转折点下标，把数组分成两个有序的子数组
2 如果转折点下标返回-1,意思是数组有序，可以直接在整个数组中查找
3返回不是-1，数组是旋转后的数组。 如果target大于等于第一个元素即A[0]，那就在左半部分数组中查找，如果target小于A[0]，那就在右半部分中寻找
【代码二】
/*********************************
* 日期：2015-01-04
* 作者：SJF0115
* 题目: 33.Search in Rotated Sorted Array
* 来源：https://oj.leetcode.com/problems/search-in-rotated-sorted-array/
* 结果：AC
* 来源：LeetCode
* 博客：
**********************************/
#include <iostream>
using namespace std;
class Solution {
public:
int search(int A[], int n, int target) {
if(n <= 0){
return -1;
}//if
// 旋转转折点
int pivot = FindPivot(A,n);
// 数组有序
if(pivot == -1){
return search(A,0,n-1,target);
}//if
if(A[pivot] == target){
return pivot;
}//if
// 数组旋转
// 在左半部分寻找
if(A[0] <= target){
return search(A,0,pivot,target);
}//if
// 在右半部分寻找
else{
return search(A,pivot+1,n-1,target);
}//else
}
private:
int search(int A[], int start,int end, int target) {
if(start > end){
return -1;
}
// 二分查找
while(start <= end){
// 中间节点
int mid = (start + end) / 2;
// 找到
if(A[mid] == target){
return mid;
}//if
// 左半部分
else if(A[mid] > target){
end = mid - 1;
}//else
// 右半部分
else{
start = mid + 1;
}//else
}//while
return -1;
}
// 寻找转折点
int FindPivot(int A[],int n){
int start = 0,end = n - 1;
// 数组有序
if(A[end] > A[start]){
return -1;
}//if
// 数组旋转
// 二分查找
while(start <= end){
int mid = (start + end) / 2;
// 转折点在[mid,end]区间中
if(A[mid] > A[start]){
start = mid;
}//if
// 转折点在[start,mid]区间中
else if(A[mid] < A[start]){
end = mid;
}//else
else{
return mid;
}
}//while
}
};
int main() {
Solution solution;
int A[] = {4,5,6,7,0,1,2};
//int A[] = {3,1};
cout<<solution.search(A,7,0)<<endl;
}
