如何修改合併排序以僅返回元素的索引而不排序？

Question

如何在不對數組進行排序的情況下遞歸地獲取某個元素的索引？

Answer 1

在這種情況下，蠻力搜索和遞歸搜索都具有相同的時間複雜度。但仍然，如果你想遞歸版本，那麼僞代碼將：

1. 調用與陣列和導航鍵的功能，以search.Init數組一個靜態指標。

2. 檢查，如果索引超出範圍的則返回-1（意味着未找到）

3. 檢查，如果在陣列的電流元件是關鍵。 如果true返回靜態索引;

4. else通過遞增索引來返回函數調用。

Answer 2

這個問題可能是指找到排序列表中某個元素的排名。實際上，這個操作並不需要顯式地對數組進行排序，而只需要計算有多少元素比它小（假設按升序排序）。

對此，最好的複雜度是O（n），因爲每個元素都需要檢查。

使用非遞歸方法實現O（n）複雜性很簡單 - 只需遍歷所有元素，並在遇到較小元素時增加計數器。計數器的最終值表示有序元素在排序數組中的位置（請注意，這是在沒有明確排序的情況下獲得的）。

一個簡單的遞歸解決辦法，（使用C風格的代碼）模仿這種行爲如下所示：

getRank(int value, int* array, int nElements) { 
    if (nElements == 0) return 0; 

    if (array[0] < value) 
     return 1 + getRank(value, array + 1, nElements - 1); 
    else 
     return getRank(value, array + 1, nElements - 1); 
}