在旋轉的排序陣列中尋找樞軸點

首先讓我說我是C新手，所以我的方法很基礎。我正在嘗試檢查一個已排序的數組的旋轉點。例如（1 2 4 5 9）變成（5 9 1 2 4）。我試圖將數組「分成」兩個子數組，並從[0]開始檢查一個，並從[4]開始增加一個，然後減少一個。以下是我迄今爲止：在旋轉的排序陣列中尋找樞軸點

#define size 5 
int main(void) 
{ 
int x, i, j, start, end; 
int array1[size]= {4, 8, 0, 1, 3}; 
start = 0; 
end = size -1; 
while(start < end) 
{ 
if (array1[start] < array1[end]) 
    start++; 
    end--;

我想一些我有問題是，如果我的做法是很好的（外到內），或者我是否應該在中間開始，然後我的出路。另外，我將如何編碼確定樞軸實際發生的位置。我在SO中看到了C++的一些答案，但是我看不到很多對C來說很清楚的答案，所以我想我會問。任何建議表示讚賞。

來源

2012-09-15 bardockyo

這個循環將持續地尋找支點元素代碼因爲'array1 [0] == 4'和'array1 [end] == 3'和'if（4 <3）'不會帶分支。 – oldrinb

我可以建議你在編譯器中試試嗎？不要看它是否是最好的解決方案，或者它是否適用於所有情況，但要查看是否存在編譯器將幫助您捕獲的一些明顯錯誤。 –

@bardockyo'start'和'end'永遠不會改變，所以循環將無限期地繼續。 – oldrinb

該問題是相當微不足道的解決。由於原始集合是排序的，只是迭代前進，直到你命中的元素小於數組中的最後一個元素 - 這是原始的第一個元素，所以你知道它從開始的距離一致到R（mod N ）其中R是旋轉距離和N是size。

int last = array[size - 1]; 
int r; 
for (r = 0; array[r] >= last; ++r) ; 
int pivot = array[r]; 
/* pivot was the original array[0] */

來源

2012-09-15 07:05:14 oldrinb

非常感謝你！ – bardockyo

這是O（n），但在O（log（n）） – Antoine

O（log（n））中有一種方法可以使用二進制搜索的概念來實現。 –

在C

int findPivot(int arr[], int low, int high) 
{ 
    // base cases 
    if (high < low) return -1; 
    if (high == low) return low; 

    int mid = (low + high)/2; /*low + (high - low)/2;*/ 
    if (mid < high && arr[mid] > arr[mid + 1]) 
    return mid; 
    if (mid > low && arr[mid] < arr[mid - 1]) 
    return (mid-1); 
    if (arr[low] >= arr[mid]) 
    return findPivot(arr, low, mid-1); 
    else 
    return findPivot(arr, mid + 1, high); 
}

，你返回-1時，數組已經排序，的東西像往常一樣休息就像一個二進制搜索

來源

2014-04-16 09:54:38 cbinder

在旋轉的排序陣列中尋找樞軸點

回答

相關問題