title: Search for first index of 'xy' in string using divide and conquer
body: <p>I have to find the <em>first instance</em> of the sub string "xy" in a char array, by using divide and conquer to split my array into half (so array[0...mid] and array[mid+1...size] where mid = size+1/2) and recursively running my algorithm on both halves. The substring 'xy' could be in the left half, it could be in the right half, or it could be between the two halves. It returns the index of 'x' if the first 'xy' is found, otherwise returns a -1. My method is allowed two parameters, the (pointer to) array and the size of the array. I tried to do it by using a modified binary search, and the code is as follows:</p>
  
  <p>(PS. this is pseudocode that resembles C++, doesn't have to be proper  just the logic has to be good)</p>
  
  <pre><code>public int xy-search(char* data, int n){ //starts at l=0 and r == n-1
  
      int l = 0; //left index
  
      int r = n-1; // right index
  
      if (n==1)
          return -1;
  
      if (l&gt;r) // not found
          return -1;
  
      int mid = l+r/2; //get mid point
  
      if (data[mid] == ‘x’ &amp;&amp; data[mid+1] == ‘y’)
          return mid;
  
      else if (l==r) // not found
          return -1;
  
      else {
          int left = xy-search(data, left); //check left
  
          int right = xy-search(data+left+1, n - left - 1); // check right
  
          if (left != -1) //if found at left, return index
              return left;
  
          if (right != -1) //if found at right, return index
              return right;
  
          else 
              return -1;
      }
  
  
  }
  </code></pre>
  
  <p>I need someone to check my work and tell me if I am going about it wrong. Also, I feel like there should be a condition that checks the left first and if that fails, then the right, as we are looking for the <em>first instance</em> of 'xy'.</p>