title: Searching for an element in a circular sorted array
body: <p>We want to search for a given element in a circular sorted array in complexity not greater than <code>O(log n)</code>.<br>
  Example: Search for <code>13</code> in <code>{5,9,13,1,3}</code>.  </p>
  
  <p>My idea was to convert the circular array into a regular sorted array then do a binary search on the resulting array, but my problem was the algorithm I came up was stupid that it takes <code>O(n)</code> in the worst case:</p>
  
  <pre><code>for(i = 1; i &lt; a.length; i++){
      if (a[i] &lt; a[i-1]){
          minIndex = i; break;
      }
  }
  </code></pre>
  
  <p>then the corresponding index of ith element will be determined from the following relation:</p>
  
  <pre><code>(i + minInex - 1) % a.length
  </code></pre>
  
  <p>it is clear that my conversion (from circular to regular) algorithm may take O(n), so we need a better one.</p>
  
  <p>According to ire_and_curses idea, here is the solution in Java:</p>
  
  <pre class="lang-java prettyprint-override"><code>public int circularArraySearch(int[] a, int low, int high, int x){
      //instead of using the division op. (which surprisingly fails on big numbers)
      //we will use the unsigned right shift to get the average
      int mid = (low + high) &gt;&gt;&gt; 1;
      if(a[mid] == x){
          return mid;
      }
      //a variable to indicate which half is sorted
      //1 for left, 2 for right
      int sortedHalf = 0;
      if(a[low] &lt;= a[mid]){
          //the left half is sorted
          sortedHalf = 1;
          if(x &lt;= a[mid] &amp;&amp; x &gt;= a[low]){
              //the element is in this half
              return binarySearch(a, low, mid, x);
          }
      }
      if(a[mid] &lt;= a[high]){
          //the right half is sorted
          sortedHalf = 2;
          if(x &gt;= a[mid] &amp;&amp; x&lt;= a[high] ){
              return binarySearch(a, mid, high, x);
          }
      }
      // repeat the process on the unsorted half
      if(sortedHalf == 1){
          //left is sorted, repeat the process on the right one
          return circularArraySearch(a, mid, high, x);
      }else{
          //right is sorted, repeat the process on the left
          return circularArraySearch(a, low, mid, x);
      }
  }
  </code></pre>
  
  <p>Hopefully this will work.</p>