[LeetCode]33.Search in Rotated Sorted Array

本文主要是介绍[LeetCode]33.Search in Rotated Sorted 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);}//ifif(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}//whilereturn -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;}//elseelse{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;
}

这篇关于[LeetCode]33.Search in Rotated Sorted Array的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---