題目

Suppose an array sorted in ascending order 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.

分析

根據(jù)一個被旋轉(zhuǎn)的排序數(shù)組，尋找某個值的位置。我是先進行快排，并使用另一個數(shù)組保存每個值的索引值，然后用二分查找目標(biāo)值，之后再輸出其索引值即可。
當(dāng)然有其他更簡單的方法。

void sort(int *a,int *index, int left, int right)
{
    if(left >= right)/*如果左邊索引大于或者等于右邊的索引就代表已經(jīng)整理完成一個組了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];
    int keyindex=index[left];
    while(i < j)                               /*控制在當(dāng)組內(nèi)尋找一遍*/
    {
        while(i < j && key <= a[j])
        /*而尋找結(jié)束的條件就是，1，找到一個小于或者大于key的數(shù)（大于或小于取決于你想升
        序還是降序）2，沒有符合條件1的，并且i與j的大小沒有反轉(zhuǎn)*/ 
        {
            j--;/*向前尋找*/
        }
         
        a[i] = a[j];
        index[i]=index[j];
        /*找到一個這樣的數(shù)后就把它賦給前面的被拿走的i的值（如果第一次循環(huán)且key是
        a[left]，那么就是給key）*/
         
        while(i < j && key >= a[i])
        /*這是i在當(dāng)組內(nèi)向前尋找，同上，不過注意與key的大小關(guān)系停止循環(huán)和上面相反，
        因為排序思想是把數(shù)往兩邊扔，所以左右兩邊的數(shù)大小與key的關(guān)系相反*/
        {
            i++;
        }
         
        a[j] = a[i];
        index[j]=index[i];
    }
     
    a[i] = key;/*當(dāng)在當(dāng)組內(nèi)找完一遍以后就把中間數(shù)key回歸*/
    index[i]=keyindex;
    sort(a, index,left, i - 1);/*最后用同樣的方式對分出來的左邊的小組進行同上的做法*/
    sort(a, index,i + 1, right);/*用同樣的方式對分出來的右邊的小組進行同上的做法*/
                       /*當(dāng)然最后可能會出現(xiàn)很多分左右，直到每一組的i = j 為止*/
}
int search(int* nums, int numsSize, int target) {
    int index[10000]={0};
    for(int i=0;i<10000;i++)
        index[i]=i;
    sort(nums,index,0,numsSize-1);
    int p=0,q=numsSize-1;
    while(p<q)
    {
        if(nums[(p+q)/2]>target)q=(p+q)/2-1;
        else if(nums[(p+q)/2]<target)p=(p+q)/2+1;
        else return index[(p+q)/2];
    }
    if(p==q&&nums[p]==target)return index[p];
    else return -1;
}