二進制搜索尋找魔術索引

我正在練習二進制搜索，當我嘗試實現它來查找數組中的「魔術索引」時，我正在碰壁。神奇指數是A[i] == i。二進制搜索尋找魔術索引

我在Java using recursion中發現了一些實現，但我試圖避免這樣做遞歸，因爲遞歸是昂貴的（我想看看二進制搜索是否適合在這裏）。

這裏是我的代碼：

function magicIndex(arr) { 
    var result = arr, mid; 
    while (result.length > 1) { 
    mid = Math.floor(result.length/2); 

    if (result[mid] === mid) { 
     return arr.indexOf(result[mid]); 
    } else if (mid > result[mid]) { 
     result = result.slice(mid+1, result.length); 
    } else { 
     result = result.slice(0, mid); 
    } 
    } 
    return arr.indexOf(result.pop()); 
}

的問題是，該算法不正確切片中的某些測試運行的陣列到反面。

例如，[-10, -3, 0, 2, 4, 8]返回4，但[-10, 1, 0, 2, 5, 8]也返回4。

來源

2017-04-04 Jose

您沒有提及該數組是排序的 – MBo

@MBo我不確定您是否試圖從OP中確認他的數組是否已排序，但是如果沒有，則二分查找假設排序，不是嗎？ – 0xc0de

@Jose，二進制搜索僅適用於已排序的數組，第二個數組未進行排序。 – 0xc0de

既然你在練習，我認爲你自己編碼對你有好處，但我會給你一個指導。

使用此算法（注意輸入數組應該已經被排序，否則實行分類法）：

int arr[n]; 
    K ← 1; //search key 
    l ← 0; r ← n - 1; 
    while l ≤ r do 
     m ← floor((l + r)/2) 
     if K = arr[m] 
      return m 
     else if K < arr[m] 
      r ← m − 1 
     else 
      l ← m + 1 
    return −1

這將輸出你的搜索鍵的索引，-1，如果關鍵是沒有找到。

來源

2017-04-04 04:02:57

這個算法不會找到一個'魔術指數'，會嗎？ OP解決方案中的邏輯對我來說似乎是正確的。 – 0xc0de

只需將鍵設置爲預期的索引。該算法用於通用目的; m←floor（（l + r）/ 2）; K←m;' –

什麼是'意向指數'？事實上，這裏不需要'K'，只需'm == arr [m]'即可。我指出，因爲OP的算法沒有問題。 – 0xc0de

您的第二個數組未被排序，並且binary search僅適用於已排序的數組。

來源

2017-04-04 05:26:39 0xc0de

謝謝，當在控制檯中進行沙盒操作時，我必須保持負面信號。 – Jose

二進制搜索尋找魔術索引

回答

相關問題