学步园

微软：
一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}

是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。 

----------------------------------------

一般情况下，数组的查找都是建立在排序的基础上的，怎样的排序就决定来怎样的查找能够最快。

例如二叉树查找，哈希查找等。

这里的数组也是属于有序数组，所以一般采用二分查找能够快速找到，时间复杂度O(logN)

既然是二分，大家都很熟悉了，注意下分类的时候可能存在一边是以往的单调序列（和往常的一样）

另一边不是

分类讨论下就好来

----

看到另一种思路：先移回来，再查找，但是这个时间复杂度上就增加来，而且最后还是二分查找。。。

//============================================================================
// Name        : DSCSearch.cpp
// Author      : YLF
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <stdio.h>
#include <malloc.h>
using namespace std;

int BSearch(int* arr, int n, int l, int h, int x);

int main() {
	int n;
	int *arr = (int*)malloc(n*sizeof(int));

	int i = 0;
	cin>>n;
	for(i=0;i<n;i++)
		cin>>arr[i];

	int x;
	cin>>x;
	cout<<BSearch(arr,n,0,n-1,x);
	return 0;
}

/*
 * 二分查找
 */
int BSearch(int* arr, int n, int l, int h, int x){
	if(l>h)
		return -1;

	int mid = (l+h)/2;
	if(arr[l]==x)
		return l;
	if(arr[h]==x)
		return h;
	if(arr[mid]==x)
		return mid;
        //分四类，其中有两类 x都比arr[l]arr[mid]大和都比他们小需要注意这个移动带来的麻烦，另外两类则不需要
	if(x>arr[mid] && x<arr[l])
		return BSearch(arr,n,l+1,mid-1,x);
	if(x<arr[mid] && x<arr[l]){
		if(arr[mid]<arr[l])
			return BSearch(arr,n,mid+1,h-1,x);
		else
			return BSearch(arr,n,l+1,mid-1,x);
	}
	if(x>arr[mid] && x>arr[l]){
		if(arr[mid]<arr[l])
			return BSearch(arr,n,mid+1,h-1,x);
		else
			return BSearch(arr,n,l+1,mid-1,x);
	}
	if(x<arr[mid] && x>arr[l])
		return BSearch(arr,n,mid+1,h-1,x);

	return -1;
}

我这里打印出该数的位置

10
7 5 4 2 1 0 12 10 9 8
9
8