title: Recursive unsorted array search algorithm in C?
body: <p>Let's say we want to write a function in C that finds a specified target value in an unsorted array of ints. In general, this is simple and runs in O(n) time:</p>
  
  <pre><code>int search(int *data, int len, int target)
  {
      int i;
      for(i = 0; i &lt; len; i++)
          if(data[i]==target) return i;
      return -1;
  }
  </code></pre>
  
  <p>Let's say we're being masochistic and want to approach this with a divide and conquer algorithm instead.  We'll run into trouble on the recursive part because we can't exclude half the array each time, like we can with binary search:</p>
  
  <pre><code>int search(int *data, int start, int stop, int target)
  {
  // Base case: we've divided the array into two size subarray
      if(stop==start+1)
  {
      if(data[start]==target) return start;
      if(data[stop]==target) return stop;
      return -1;
  }
  /* The recursion part is tricky.  
      We *need* to parse both halves of the array, because we can't safely
      exclude any part of the array; it's not sorted, so we can't predict
      which half it's going to be in.*/
  else
  {
      /** This obviously doesn't work. */
      int mid = (stop-start)/2;
      return search(data, start, mid, target);
      return search(data, mid+1, stop, target);
  }
  }
  </code></pre>
  
  <p>Is there any way to make this work?</p>
  
  <p>NOTE: This is <em>not</em> asking people to do my homework for me, as some of you may think when reading this question.  It is, however, inspired by curiosity after I encountered this problem when trying to solve a question in an assignment that I've submitted earlier this week.</p>