題目描述：

一個(gè)數(shù)組是由一個(gè)遞減數(shù)列左移若干位形成的，比如{4，3，2，1，6，5}是由{6，5，4，3，2，1}左移兩位形成的，在這種數(shù)組中查找某一個(gè)數(shù)。

?

解析：

很多解法的時(shí)間復(fù)雜度都停留在O(n)，下面的解法 仍為二分查找法 只不過 對應(yīng)題目做了相應(yīng)的改進(jìn) 時(shí)間復(fù)雜度為O(log₂n)

?

1.思路：(畫圖實(shí)際上更直觀看出來思路，讀者試著自己畫出圖來對應(yīng)分析)

設(shè)數(shù)組a[start]~a[end],mid = (start + end) / 2 在進(jìn)行二叉查找時(shí)，待查找數(shù)肯定會(huì)在變量mid的兩側(cè)，其中mid的取值主要有以下幾情況，

第一種為a[mid] < a[start] 說明此時(shí)mid對應(yīng)的數(shù)字在最大數(shù)的左邊， 第二種為a[start]? > a[end] 說明此時(shí)mid對應(yīng)的數(shù)字在最大數(shù)的右邊，這兩種情況對應(yīng)不同的判斷計(jì)算方法，詳見下面的代碼，其他情況不是違反題意就是容易得出結(jié)果。

?

2.代碼

#include <iostream>using namespace std;int find(int *a ,int x, int max) {int start = 0, end = max - 1;while(start < end - 1){int mid = start + (end - start)/2;if(a[start] == x)return start;if(a[end] == x)return end;if(a[mid] == x)return mid;if(a[mid] < a[start] ){if( x < a[start] && x > a[mid])end = mid ;elsestart = mid ;}else if(a[mid] > a[end]){if( x > a[end] && x < a[mid])start = mid ;elseend = mid ;}else{if (x != a[mid])return -1;elsereturn mid;}}return -1; }int main() {int a[10] = {4, 3, 2, 1, 10 ,9, 8,7, 6, 5};int index = find(a, 8, 10);cout << "index:" << index << endl;return 0; }

?

?

3.執(zhí)行效果：

?

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/biyeymyhjob/archive/2012/09/19/2693879.html

總結(jié)

以上是生活随笔為你收集整理的在移位数组中查找数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。