Search in Rotated Sorted Array--LeetCode

题目：

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.

思路：类似于二分查找，需要注意的是在查找的时候锁定在某一个范围内查找，因为对于这样的数组，总是可以通过二分查找来找出一段空间上的数据是单调的，可以根据查找元素的情况来判断是否在这段单调空间内查找这个元素。

如果vec[mid] == key,那么当前位置就是目标元素。

如果vec[mid] > vec[low]说明前半部分空间是递增的，查看key是否在这个空间内。

如果vec[mid] <=vec[low]说明后半部分是单调的，判断key是否存在这个空间内。

这里的关键是找到一个单调的空间。然后判断目标元素是否在这个单调的空间内。

如果使用目标元素来和中间元素的值进行比较来进行切割，这是很麻烦的过程，倒不如找到一个单调的空间，进而判断目标值是否存在这个单调的空间内这样来的简单。

#include <iostream> 
#include <vector>
#include <string>
using namespace std;
/*
在一个旋转数组中查找一个数 
*/
bool RotatedArray(vector<int>& vec,int key)
{
	int low =0,high= vec.size()-1;
	int mid;
	while(low <= high)
	{
		cout<<low<<" "<<high<<endl;
		mid = low+(high-low)/2;
		if(vec[mid] == key)
			return 1;
		if(vec[mid] > vec[low]) // 前半一定是升序 
		{
			if(key >=vec[low] && key <vec[mid]) 
				high = mid-1;
			else
				low = mid+1;
		}
		else   // 
		{
			if(key>vec[mid]&& key<=vec[high])
				high = mid-1;
			else
				low = mid+1;
		}
		
	}
	return 0;
}
int main() 
{
	
	int array[]={4,5,6,7,0,1,2};
	vector<int> vec(array,array+sizeof(array)/sizeof(int));
	cout<<RotatedArray(vec,8)<<endl;
	return 0;
}

Search in Rotated Sorted Array-LeetCode

题目：

相关推荐