QuestionAsk Questions?

View Answers

June 5, 2009 at 1:00 PM

/*

* To change this template, choose Tools | Templates

* and open the template in the editor.

*/

package javaapplication1;

import java.io.BufferedReader;

import java.io.InputStreamReader;

/**

*

* @author Satish

*/

public class BinarySearch {

public static final int NOT_FOUND = -1;

public static int binarySearch( Comparable [ ] a, Comparable x )

{

return binarySearch( a, x, 0, a.length -1 );

}

/**

* Hidden recursive routine.

*/

private static int binarySearch( Comparable [ ] a, Comparable x,

int low, int high )

{

if( low > high )

return NOT_FOUND;

int mid = ( low + high ) / 2;

if( a[ mid ].compareTo( x ) < 0 )

return binarySearch( a, x, mid + 1, high );

else if( a[ mid ].compareTo( x ) > 0 )

return binarySearch( a, x, low, mid - 1 );

else

return mid;

}

// Test program

public static void main( String [ ] args )

{

int SIZE = 8;

Comparable [ ] a = new Integer [ SIZE ];

for( int i = 0; i < SIZE; i++ )

a[ i ] = new Integer( i * 2 );

try{

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int num ;

num =Integer.parseInt(br.readLine());

System.out.println( "Found " + num + " at " +

binarySearch( a, new Integer( num ) ) );

}

catch(Exception e)

{}

}

}

* To change this template, choose Tools | Templates

* and open the template in the editor.

*/

package javaapplication1;

import java.io.BufferedReader;

import java.io.InputStreamReader;

/**

*

* @author Satish

*/

public class BinarySearch {

public static final int NOT_FOUND = -1;

public static int binarySearch( Comparable [ ] a, Comparable x )

{

return binarySearch( a, x, 0, a.length -1 );

}

/**

* Hidden recursive routine.

*/

private static int binarySearch( Comparable [ ] a, Comparable x,

int low, int high )

{

if( low > high )

return NOT_FOUND;

int mid = ( low + high ) / 2;

if( a[ mid ].compareTo( x ) < 0 )

return binarySearch( a, x, mid + 1, high );

else if( a[ mid ].compareTo( x ) > 0 )

return binarySearch( a, x, low, mid - 1 );

else

return mid;

}

// Test program

public static void main( String [ ] args )

{

int SIZE = 8;

Comparable [ ] a = new Integer [ SIZE ];

for( int i = 0; i < SIZE; i++ )

a[ i ] = new Integer( i * 2 );

try{

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int num ;

num =Integer.parseInt(br.readLine());

System.out.println( "Found " + num + " at " +

binarySearch( a, new Integer( num ) ) );

}

catch(Exception e)

{}

}

}

Related Tutorials/Questions & Answers: