title: Binary Search for finding Magic Index
body: <p>I'm practicing binary search and I'm running into a wall when trying to implement it to find the "magic index" in an array. The magic index is <code>A[i] == i</code>.</p>
  
  <p>I've found some implementations in <a href="http://comproguide.blogspot.com/2014/02/finding-magic-index-of-array.html" rel="nofollow noreferrer">Java using recursion</a>, but I'm trying to avoid doing this recursively because recursion is expensive (and I want to see if binary search is appropriate here).</p>
  
  <p>Here is my code:</p>
  
  <pre><code>function magicIndex(arr) {
    var result = arr, mid;
    while (result.length &gt; 1) {
      mid = Math.floor(result.length / 2);
  
      if (result[mid] === mid) {
        return arr.indexOf(result[mid]);
      } else if (mid &gt; result[mid]) {
        result = result.slice(mid+1, result.length);
      } else {
        result = result.slice(0, mid);
      }
    }
    return arr.indexOf(result.pop());
  }
  </code></pre>
  
  <p>The problem is that the algorithm incorrectly slices the array to the wrong side on certain test runs.</p>
  
  <p>For example, <code>[-10, -3, 0, 2, 4, 8]</code> returns <code>4</code>, but <code>[-10, 1, 0, 2, 5, 8]</code> returns <code>4</code> as well. </p>