Pooja Oza

Greenhorn

Posts: 21

posted 8 years ago

import java.utils.Arrays.*;

public class BinarySearch

{

public static final int NOT_FOUND = -1;

/**

* Performs the standard binary search

* using two comparisons per level.

* @return index where item is found, or NOT_FOUND.

*/

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

{

int low = 0;

int high = a.length - 1;

int mid;

while( low <= high )

{

mid = ( low + high ) / 2;

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

low = mid + 1;

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

high = mid - 1;

else

return mid;

}

return NOT_FOUND; // NOT_FOUND = -1

}

// 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 );

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

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

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

}

}

The output is :

Found 0 at 0

Found 1 at -1

Found 2 at 1

Found 3 at -1

Found 4 at 2

Found 5 at -1

Found 6 at 3

Found 7 at -1

Found 8 at 4

Found 9 at -1

Found 10 at 5

Found 11 at -1

Found 12 at 6

Found 13 at -1

Found 14 at 7

Found 15 at -1

**Please explain me how the binarySearch method works normally and also in the below program?**

import java.utils.Arrays.*;

public class BinarySearch

{

public static final int NOT_FOUND = -1;

/**

* Performs the standard binary search

* using two comparisons per level.

* @return index where item is found, or NOT_FOUND.

*/

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

{

int low = 0;

int high = a.length - 1;

int mid;

while( low <= high )

{

mid = ( low + high ) / 2;

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

low = mid + 1;

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

high = mid - 1;

else

return mid;

}

return NOT_FOUND; // NOT_FOUND = -1

}

// 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 );

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

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

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

}

}

The output is :

Found 0 at 0

Found 1 at -1

Found 2 at 1

Found 3 at -1

Found 4 at 2

Found 5 at -1

Found 6 at 3

Found 7 at -1

Found 8 at 4

Found 9 at -1

Found 10 at 5

Found 11 at -1

Found 12 at 6

Found 13 at -1

Found 14 at 7

Found 15 at -1

**Please help me out with this, i am preparing for scjp exam and stuck with this method. I am really confused how a binarySearch() method works in Java, please explain me in detail**

Thanks,

Pooja Oza

Rafael Angarita

Ranch Hand

Posts: 67

Pooja Oza

Greenhorn

Posts: 21

Ryan Beckett

Ranch Hand

Posts: 192

posted 8 years ago

The iterative loop has a point mid (the middle element) and it compares it with the number your searching for. If the number is less than mid, during the next iteration the tail becomes mid, and the comparison is made again. If the number is greater than mid, the head becomes mid, etc. The data gets chopped by half every iteration, hence the term "Binary".

Always, remember the data must be sorted for the search to work. Otherwise, the search isn't guaranteed to work.

You can substitute your main method with this to see what I mean.

Good luck.

**binarySearch(a, 11)**

Itr

___lo_________mi_________high

1-> |0|1|2|3|4|5|6|7|8|9|10|11|12|

______________lo____mi____high

2-> |0|1|2|3|4|5|6|7|8|9|10|11|12|

___________________lo_mi__high

3-> |0|1|2|3|4|5|6|7|8|9|10|11|12|

_____________________lo_mi_high

4-> |0|1|2|3|4|5|6|7|8|9|10|11|12|

Found at index 11.Itr

___lo_________mi_________high

1-> |0|1|2|3|4|5|6|7|8|9|10|11|12|

______________lo____mi____high

2-> |0|1|2|3|4|5|6|7|8|9|10|11|12|

___________________lo_mi__high

3-> |0|1|2|3|4|5|6|7|8|9|10|11|12|

_____________________lo_mi_high

4-> |0|1|2|3|4|5|6|7|8|9|10|11|12|

Found at index 11.

Always, remember the data must be sorted for the search to work. Otherwise, the search isn't guaranteed to work.

You can substitute your main method with this to see what I mean.

Good luck.