826
[LeetCode]33.Search in Rotated Sorted 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.
【分析】
循環遞增數組有這麼一個性質：以數組中間元素將循環遞增數組劃分為兩部分，則一部分為一個嚴格遞增數組，而另一部分為一個更小的循環遞增數組。
當中間元素大於首元素時，前半部分為嚴格遞增數組，後半部分為循環遞增數組；當中間元素小於首元素時，前半部分為循環遞增數組；後半部分為嚴格遞增數組。
【代碼】
/*********************************
* 日期：2014-01-15
* 作者：SJF0115
* 題號: 33.Search in Rotated Sorted Array
* 來源：https://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;
}
最後更新：2017-04-03 12:54:31