@xixi003

Leetcode-Search Rotated 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.

思路

在有序数组中查询一个值，二分法是一个通用解法。本题虽然在某一个地方，将数组分段了，依旧可以沿用这种方法。

假设现在我们要在A[l] … A[r]中查询target。

  • 1.A[l] < A[r]，说明A[l] < A[l + 1] < A[l + 2] < … < A[r]是一个部分有序数组，可以直接采用二分查询；
  • 2.A[l] > A[r]，说明存在一个k，使得A[l]到A[k]，A[k+1]到A[r]为两个有序数组，此时我们还是用二分处理：

参考代码

AC代码

#include <iostream>

using namespace std;

int search(int A[], int n, int target)
{
    	int left = 0;
    	int right = n - 1;
    	while(left < right)
    	{
    		int mid = left + (right - left) / 2;  //bin sort
    		if(A[mid] >= A[left] ) //if left side sorted
    		{
    			if(A[left] <= target && target <= A[mid])
    				right = mid;
    			else
    				left = mid + 1;
    		}
    		else //if right side sorted
    		{
    			if(A[mid] <= target && target <= A[right])
    				left = mid;
    			else
    				right = mid - 1;
    		}
    	}
    	if(right >= 0 && right < n && A[right] == target)
    		return right;
    	else
    		return -1;
}

int main()
{
    	int n;
    	cin>>n;
    	int A[n];
    	for(int i = 0; i < n; i++)
    		cin>>A[i];
    	int target;
    	cin>>target;
    	
    	cout<<search(A, n, target)<<endl;
    	return 0;
}