title: Algorithm to find if there is any i so that array[i] equals i
body: <p>I've got an assignment from my CS professor:</p>
  
  <p>Find, in O(logn) time, if in a given pre-sorted array of distinct integers there is an index i so that array[i] = i. Prove that the time is O(logn).</p>
  
  <p><em>Update:</em> Integers can be negative, 0 or positive.</p>
  
  <p>Alright, So I have struggled a bit with this. My idea is this:</p>
  
  <p>Using binary search, we can only be certain that there is no such value to the left of the middle element if array[mid] &lt;= startindex, where mid is index of middle element, and startindex is the start of the array.</p>
  
  <p>Corresponding rule for the right half of an array is that array[mid] >= startindex + numel, where variables as above and numel is the number of elements right of mid.</p>
  
  <p>This doesn't seem like O(logn), since in the worst case I have to iterate through the whole thing, right? Can someone tip me in the right direction here, or tell me this works?</p>
  
  <p>Any ideas how I could formally prove this? I'm not asking for a definite answer, more some help to make me understand.</p>
  
  <p>In C:</p>
  
  <pre><code>int _solve_prob_int(int depth, int start, int count, int input[])
      {
      if(count == 0)
          return 0;
      int mid = start + ((count - 1) / 2);
      if(input[mid] == mid)
          return 1;
  
      if(input[mid] &lt;= start &amp;&amp; input[mid] &gt;= start + count)
          return 0;
  
      int n_sub_elleft = (int)(count - 1) / 2;
      int n_sub_elright = (int)(count) / 2;
  
      if(input[mid] &lt;= start)
          return _solve_prob_int(depth + 1, mid + 1, n_sub_elright, input);
  
      if(input[mid] &gt;= start + count)
          return _solve_prob_int(depth + 1, mid - n_sub_elleft, n_sub_elleft, input);
  
      return _solve_prob_int(depth + 1, mid - n_sub_elleft, n_sub_elleft, input) ||
              _solve_prob_int(depth + 1, mid + 1, n_sub_elright, input);
      }
  </code></pre>
  
  <p>A test case:</p>
  
  <pre><code>Sorted args: 1 2 3 4 5 6 7 8 9 10 11 12 : 
  Start: 0, count: 12, mid: 5 value: 6
      Start: 0, count: 5, mid: 2 value: 3
          Start: 0, count: 2, mid: 0 value: 1
              Start: 1, count: 1, mid: 1 value: 2
          Start: 3, count: 2, mid: 3 value: 4
              Start: 4, count: 1, mid: 4 value: 5
      Start: 6, count: 6, mid: 8 value: 9
          Start: 6, count: 2, mid: 6 value: 7
              Start: 7, count: 1, mid: 7 value: 8
          Start: 9, count: 3, mid: 10 value: 11
              Start: 9, count: 1, mid: 9 value: 10
              Start: 11, count: 1, mid: 11 value: 12
  </code></pre>
  
  <p>The above is my program run with some output according to how it searched. With a list from 1 - 12 it pivots around index 5, determines that there could be a value between 0-4 at indexes 0-4. It also determines that there could be a value between 6-11 at indexes 6-11. Thus, I proceed to search them both. Is this wrong?</p>