Search in Rotated Sorted Array--LeetCode

红太狼 2022-08-05 13:14 7阅读 0赞

# 题目： #

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])
    				low = mid+1;
    			else
    				right = 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;
    }

ps:这个题目和在旋转数组中招最小值非常饿相似，都是先确定那一部分是单调的，但是在单调的区间中查找有区别，因为查找最小值时，单调区间时没必要查找的，但是在查找某个值时，需要判断目标值和单调区间的关系在确定查找的范围