Q
一個遞增數(shù)列把后幾項整體移動到最前面吗跋，移動幾項并不知道卷玉，例如：數(shù)列123456789哨颂，移動后3項，數(shù)列變?yōu)?89123456相种。對于這樣的數(shù)列威恼，給定一個數(shù)，查找該數(shù)在數(shù)列中的下標，如果不存在則返回-1箫措。
A
算法分析
對于一個有序的數(shù)組腹备，最快的是二分查找，時間復雜度是θ(logn)斤蔓。本題只是二分查找的一個變形植酥，所以可以以二分查找為基礎(chǔ)，寫出算法弦牡。
本題的關(guān)鍵是如何進行正確的遞歸友驮，也就是判斷key在哪一半中。函數(shù)newBs中對6種情況分別進行了判斷驾锰，之后調(diào)用newBs或者bs進行遞歸卸留。因為每一次遞歸只有常數(shù)次判斷，所以最終的時間復雜度和二分查找是一樣的稻据，均是θ(logn)艾猜。
C++實現(xiàn)
#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;
}
