Index Match

Comments

• 

  曾國峻  

  Feb 14, 10:04 PM

  I have implemented binary search by recursion.
  Here is my code:

  static void doStuff(int[] ar){
  //your code here
  int low = 0;
  int high = ar.length-1;

  cont...

  int record = 0;
  for(int i=0; i<ar.length; i++)
  {
      record = record + find(low,high,ar,i);
  }
  if(record == ar.length*(-1))
      System.out.print(-1);   
  

  }

  static int find(int low,int high,int[] ar,int i){
  int mid = (low+high)/2;

  if (high<low)
  {
      return -1;
  }
  
  if (ar[i] > ar[mid])
  {
      return find(mid+1,high,ar,i);
  }
  else if (ar[i] < ar[mid])
  {
      return find(low,mid-1,ar,i);
  }
  else 
  {
      System.out.print(ar[i] + " ");
      return 0;
  }
  

  }

  I can't figure out what wrong with it.
  Could anyone can give me some advices?

• 

  Paul  

  May 10, 9:13 AM

  曾國峻 I needed to keep track of the index and pass it back up the recursion to solve it. Because each time the binary search needed to look at the > side of the array, the index forgets about the lower half of the array. Here is my solution in Ruby:

  cont...

  def index_match(ar, index=0)

  mid = ar.length/2
  actual_index = mid + index
  
  if ar[mid] == actual_index
      return actual_index
  elsif ar.length == 1
      return -1
  elsif ar[mid] < mid
      index_match(ar[(mid + 1)..-1], actual_index + 1)
      # here is where we check the > side of the array, and need to pass the index to keep track of it (or it keeps returning to 0)
  else # ar[mid] > mid
      index_match(ar[0..(mid - 1)], index)
  end
  

  end

• 

  mike  

  Sep 4, 3:05 PM

  Better to solve without recursion. maybe can be a bit more elegant, but works.

      int start = 0;
      int end = ar.length-1;
  
      int i = start + ((end - start) / 2);
  

  cont...

      while (start < end && ar[i] != i){
        if(ar[i] > i){
          if(end == i){
            break;
          }
          end = i;
        } else {
          if(start == i){
            break;
          }
          start = i;
        }
        i = start + ((end - start) / 2);
      }
      if(ar[i] == i){
        System.out.println(i);
      } else {
        System.out.println(-1);
      }