バイナリ検索マジックインデックス

Question

を見つけるために、私は、バイナリ検索を練習だし、配列内の「魔法のインデックス」を見つけるために、それを実装しようとしたとき、私は壁に実行していますよ。魔法指数は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を返します。

Answer 1

あなたが練習しているので、私はあなたが自分でそれをコーディングすることが良いと思いますが、私はあなたのガイドを与えるでしょう。 、この意志出力、検索キーのインデックス

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鍵が見つからない場合：

は、このアルゴリズムを（そうでない場合はソート方法を実装し、その入力配列がすでにソートされなければならない注意してください）を使用してください。

Answer 2

あなたの二番目の配列をソートし、ソートされただけアレイ上binary search作品されていません。