recursive binary search : used code may have alternative?

[Leonidas Savvides]

SUBJECT:recursive binary search : used code may have alternative...?

I used

      } else if (first == upto) {
		if (key == sorted[first]) {
				return first;   // Found it.
		}
    }  

you think is correct? any other solution? it works!

     public int binarySearch( int key )
   {
   return rBinarySearch(this.data,0, data.length-1, key);
   }
   public int rBinarySearch(int[] sorted, int first, int upto, int key) {
    
    if (first < upto) {
        int mid = (first + upto+1) / 2;  // Compute mid point.
        if (key < sorted[mid]) {
            return rBinarySearch(sorted, first, mid-1, key);
            
        } else if (key > sorted[mid]) {
            return rBinarySearch(sorted, mid+1, upto , key);
            
        } else {
            return mid;   // Found it.
        }
    } else if (first == upto) {
		if (key == sorted[first]) {
				return first;   // Found it.
		}
    }
    return -1;  // Failed to find key
   }  

[Lavanya Halliwell]

definitely an interesting problem, I tried this and if I start my "sorted" array at 1 I get 1 less then the key as a final result (1,2,3,4,5....). If I start it at 0 I get the key. (0,1,2,3,4,5...)

with "sorted" as {0,1,2,3,4,5,6,7,8,9} and key = 5

first: start=5 end=end

second: start=5 end=7

anyway, here is my netbeans code....

    

public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int [] sorted = {0,1,2,3,4,5,6,7,8,9};
        System.out.println(rBinarySearch(sorted,0, sorted.length-1, 5));
    }



   public static int rBinarySearch(int[] sorted, int first, int upto, int key) {

    if (first < upto) {
        int mid = (first + upto+1) / 2;  // Compute mid point.
        if (key < sorted[mid]) {
            return rBinarySearch(sorted, first, mid-1, key);

        } else if (key > sorted[mid]) {
            return rBinarySearch(sorted, mid+1, upto , key);

        } else {
            return mid;   // Found it.
        }
    } else if (first == upto) {
        if (key == sorted[first]) {
                return first;   // Found it.
        }
    }
    return -1;  // Failed to find key
   }

}

anyway, seems to work great if I start the list at 0

[Vineet Kakati]

The part of code mentioned in beginning is not really required;
also mid = (first+upto)/2;

consider the foll. code:-

  
 public int rBinarySearch(int[] sorted, int first, int upto, int key) 
{  
         if(first>upto)
             return (-1);      //key not found 
         int mid = (first + upto) / 2;  // Compute mid point.  
         if (key < sorted[mid]) 
         {  
             return rBinarySearch(sorted, first, mid-1, key);                 
         } 
         else if (key > sorted[mid]) 
        {  
             return rBinarySearch(sorted, mid+1, upto , key);  
         } 
         else 
         {  
             return mid;   // Found it.  
         }  
     }  
    }    

I also don't see the point of having two seperate functions binary search and rbinarysearch;

[Leonidas Savvides]

Without

        } else if (first == upto) {   
        if (key == sorted[first]) {   
                return first;   // Found it.   
        }   
        }    

if is odd or/and even the number of elements in array[i forget whichone of two], the first element does not return 0 ...however second element corrntly returns 1...

[Vineet Kakati]

I didn't get you properly;

But my code works perfectly whether number of elements in array are odd or even(array is sorted in ascending order).

[Leonidas Savvides]

is about search NOT sort, if you key=element in 0 index, then works? I will check yours later...

[Vineet Kakati]

Yes my code works even if key is element at index 0.The function returns 0 in that case;

[Leonidas Savvides]

Your code (lastly code scriptlet) tested by me and works, thks for the tip...Also my code considered wrong, hence still works?
Is wrong / May used

[Campbell Ritchie]

Leonidas Savvides wrote:Your code (lastly code scriptlet) tested by me and works, thks for the tip...Also my code considered wrong, hence still works?
Is wrong / May used

Don't understand. And your use of abbreviations like thks doesn't help.

[Leonidas Savvides]

Your code (lastly code scriptlet) tested by me and works GOOD,
thanks for this tip...

Also my code considered wrong, since still works?
Is wrong / May used

[Rob Spoor]

Just as there are many roads that lead to Rome, there are many solutions to any program. In the end, if your solution works (and is tested successfully with multiple inputs, both with and without matches) then it is a correct solution.