变形递增数列的二分查找算法

Q

一个递增数列把后几项整体移动到最前面，移动几项并不知道，例如：数列123456789，移动后3项，数列变为789123456。对于这样的数列，给定一个数，查找该数在数列中的下标，如果不存在则返回-1。

A

算法分析

对于一个有序的数组，最快的是二分查找，时间复杂度是θ(logn)。本题只是二分查找的一个变形，所以可以以二分查找为基础，写出算法。

本题的关键是如何进行正确的递归，也就是判断key在哪一半中。函数newBs中对6种情况分别进行了判断，之后调用newBs或者bs进行递归。因为每一次递归只有常数次判断，所以最终的时间复杂度和二分查找是一样的，均是θ(logn)。

C++实现

#include <iostream>
using namespace std;

int bs(const int *arr, int low, int high, int key)
{       
    int mid = low+(high-low)/2;
    if (low > high) {
        return -1;
    }
    if (arr[mid] == key) {
        return mid;
    } else if (arr[mid] > key) {
        return bs(arr, low, mid-1, key);
    } else
        return bs(arr, mid+1, high, key);
}

int newBs(const int *arr, int low, int high, int key)
{
    if (low > high)
        return -1;
    int mid = low+(high-low)/2;
    if (arr[mid] == key)
        return mid;
    if (arr[high] == key)
        return high;
    if (arr[low] == key)
        return low;
    
    if (key > arr[high]) {
        if (key < arr[mid]) {
            return bs(arr, low, mid-1, key);
        } else if (arr[mid] > arr[high]) {
            return newBs(arr, mid+1, high, key);
        } else {
            return newBs(arr, low, mid-1, key);
        }
    } else {
        if (key > arr[mid]) {
            return bs(arr, mid+1, high, key);
        } else if (arr[mid] < arr[high]) {
            return newBs(arr, low, mid-1, key);
        } else {
            return newBs(arr, mid+1, high, key);
        }
    }
}

int main(int argc, const char * argv[])
{
    const int arr[] = {10,11,16,1,2,3,4,5,6,7,8,9};
    int length = sizeof(arr)/sizeof(int);
    
    for (int i = 0; i < length; i++) {
        int result = newBs(arr, 0, length-1, arr[i]);
        cout << "result: " << result << endl;
    }

    return 0;
}