面试题 11：旋转数组的最小数字

11_MinNumberInRotatedArray.cpp

// QuickSort
int Partition(int data[], int length, int start, int end) {
    if(data == nullptr || length <= 0 || start < 0 || end >= length) {
        throw new std::exception("Invalid parameters");
    }
    // 生成随机数
    int index = RandomInRange(start, end);
    // 交换两个数字，不交换指针
    Swap(&data[index], &data[end]);
    int small = start - 1;
    for(index = start; index < end; ++index) {
        if(data[index] < data[end]) {
            ++small;
            if(small != index) {
                Swap(&data[index], &data[small]);
            }
        }
    }
    ++small;
    Swap(&data[small], &data[end]);
    return small;
}

void QuickSort(int data[], int length, int start, int end) {
    if(start == end) {
        return;
    }
    int index = Partition(data, length, start, end);
    if(index > start) {
        QuickSort(data, length, start, index - 1);
    }
    if(index < end) {
        QuickSort(data, length, index + 1, end);
    }
}

// MinNumberInRotatedArray
int Min(int *numbers, int length) {
    if(numbers == nullptr || length <= 0) {
        throw new std::exception("Invalid parameters");
    }
    int index1 = 0;
    int index2 = length - 1;
    int indexMid = index1;
    while(numbers[index1] >= numbers[index2]) {
        if(index2 - index1 == 1) {
            indexMid = index2;
            break;
        }
        indexMid = (index1 + index2) / 2;
        if(numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1]) {
            return MinInOrder(numbers, index1, index2);
        }
        if(numbers[indexMid] >= numbers[index1]) {
            index1 = indexMid;
        }
        else if(numbers[indexMid] <= numbers[index2]) {
            index2 = indexMid;
        }
    }
    return numbers[indexMid];
}

int MinInOrder(int *numbers, int index1, int index2) {
    int result = numbers[index1];
    for(int i = index1 + 1; i <= index2; ++i) {
        if(result > numbers[i]) {
            result = numbers[i];
        }
    }
    return result;
}