LeetCode Search in Rotated Sorted Array

    Description:
        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.

/**************************************************************************

    Copyright:MyCompany

    Author: Zoe

    Date:2018-02-07

    Description:
        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.

**************************************************************************/

#include "SerrchRotatedSortArr.h"
#define MAX 100

#include <iostream>
#include <stdio.h>
#include <algorithm>

using namespace std;


int cmp (int a, int b)
{
    return a > b;
}

/*
    Name: input_random_array
    Description: Generate a random array which sorted by SortType
    parameter 1: length, length of generated array
    parameter 2: type, sort type
*/
int *SerrchRotatedSortArr::input_random_array(int length, SortType type)
{
    int *array = new int[length];
    if (length <= 0 || length > 512) {
        cout<<"The array length must in 1~512\n"<<endl;
        return NULL;
    }

    srand((unsigned)time( NULL ));
    for (int i = 0; i < length; i++) {
        array[i] = rand() % MAX;
    }

    cout << "The random array is: " << endl;
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
    cout << endl;

    if (type == FROM_LITTLE_TO_BIG) {
        sort(array, array + length);
    } else if (type == FROM_BIG_TO_LITTLE) {
        sort(array, array + length, cmp);
    }

        cout << "The sorted array is: " << endl;
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
    cout << endl;

    return array;
}

int SerrchRotatedSortArr::rm_dup_item(int *sortedArr, int length)
{
    int index = 0;
    for (int i = 0; i < length; i++)
    {
        if (sortedArr[index] != sortedArr[i]) {
            sortedArr[++index] = sortedArr[i];
        }
    }
    return index + 1;
}

int SerrchRotatedSortArr::FindItemFromArray(int *Array, int startIndex, int endIndex, int exceptItem)
{
    if ((endIndex - startIndex) == 1) {
        //最后相邻的两个元素，直接比较
        if (Array[startIndex] == exceptItem) {
            return startIndex;
        } else if (Array[endIndex] == exceptItem) {
            return endIndex;
        } else {
            return -1;
        }
    }

    int ret;
    int cmpIndex = (startIndex + endIndex) / 2;

    if (exceptItem < Array[cmpIndex]) {
        ret = FindItemFromArray(Array, startIndex, cmpIndex, exceptItem);
    } else if (exceptItem > Array[cmpIndex]) {
        ret = FindItemFromArray(Array, cmpIndex, endIndex, exceptItem);
    } else {
        ret = cmpIndex;
    }
    return ret;
}

int SerrchRotatedSortArr::SearchRotatedSortedArray(int *Array, int length, int exceptItem)
{
    int index = FindItemFromArray(Array, 0, length - 1, exceptItem);
    cout << "index is " << index << endl;
    int temp[index];

    //保留前index+1个元素到temp
    for (int i = 0; i < index; i++) {
        temp[i] = Array[i];
    }

    //将后面 length - index -1 个元素搬到数组最前端
    for (int i = 0; i < (length - index); i++) {
        Array[i] = Array[i+index];
    }

    //将temp中的元素搬到数组的后端
    for (int i = 0; i < index; i++) {
        Array[length - index + i] = temp[i];
    }

    cout << "Rotated Array:" << endl;
    for (int i = 0; i < length; i++) {
        cout << Array[i] << " ";
    }
    cout << endl;
    return 0;
}

#ifndef SERRCHROTATEDSORTARR_H_INCLUDED
#define SERRCHROTATEDSORTARR_H_INCLUDED

typedef enum sort_type {
    FROM_LITTLE_TO_BIG = 0,
    FROM_BIG_TO_LITTLE = 1,
    IVALID_SORT_TYPE,
}SortType;

class SerrchRotatedSortArr {
public:
    int *input_random_array(int length, SortType type);
    int rm_dup_item(int *sortedArr, int length);
    int SearchRotatedSortedArray(int *Array, int length, int exceptItem);

private:
    int FindItemFromArray(int *Array, int startIndex, int endIndex, int exceptItem);

};



#endif // SERRCHROTATEDSORTARR_H_INCLUDED

main中执行的代码段

    SerrchRotatedSortArr serrchRotatedSortArr;
    int ArraySize = 50;
    int *Array = serrchRotatedSortArr.input_random_array(ArraySize, FROM_LITTLE_TO_BIG);
    int index = serrchRotatedSortArr.rm_dup_item(Array, ArraySize);
    for (int i = 0; i < index; i++) {
        cout << Array[i] << " ";
    }
    cout << endl;
    serrchRotatedSortArr.SearchRotatedSortedArray(Array, index, Array[21]);

执行结果：