Binary Search in java

Binary Search in java


Binary Search in java is generally used to search in a sorted array. The implementation is based on following things. The item which we trying to search is first checked by the middle value of an array. If value matches then search completes and returns.
If search item is less than the middle value then item is searched in lower half of the sorted array. If search item is greater than the value then it is searched in upper half of sorted array.

Performance of binary search in java
We can see difference when it comes to search in large numbers. Binary search in java provides O ( long n ) performance like for searching in million number of items it gives result in max 20 comparisons which is far better than linear search where it needs 500000 comparisons in worst case. Thus we can see that doing Binary Search in java is better than linear search. But binary search in java comes at a cost, we need to sort the array first and sorting is not fast. So if you are having small number of arrays then binary search in java is not good as we are first sorting the array and doing binary search on it.

But we need to consider or remember here is we need to sort an array before doing a binary search in java.

Now lets see how we can implement binary search in Java :

Binary Search in Java Example



//Method to implement binary search in java  - binary search example in java
public class BinarySearchDemo {
    public static int binarySearch( Comparable [ ] a, Comparable x )
    {
        int lowerVal = 0;
        int higherVal = a.length - 1;
        int midVal;

        while( lowerVal <= higherVal )
        {
            System.out.println("Lower val "+lowerVal+ " Higher val "+higherVal  );
            midVal = ( lowerVal + higherVal ) / 2; // Finding mid value using lower value plus higher value divided by two.
            System.out.println("Mid val :"+midVal );
            System.out.println("Search Item  : " + x );
            if( a[ midVal ].compareTo( x ) < 0 ){ // Searching in lower half using compareTo method.
                System.out.println("Searching in lower half : " + lowerVal );
                lowerVal = midVal + 1;
            }
            else if( a[ midVal ].compareTo( x ) > 0 ){ // Searching in upper half using compareTo method
                higherVal = midVal - 1;
                System.out.println("Searching in upper half : " + higherVal );
            }
            else
                return midVal;
        }

        return -1;     // NOT_FOUND = -1
    }


    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  );
       
       System.out.println( "binary search in Java");
       System.out.println( "======================================");
       System.out.println( "Search operation 1 : SEARCH ITEM 5 " );

       System.out.println( "Found 5 on index : " +
                                 binarySearch( a, new Integer( 5 ) ) );
       System.out.println( "======================================");
       System.out.println( "Search operation 1 : SEARCH ITEM 5 " );

       System.out.println( "Found 7 on index : " +
                                 binarySearch( a, new Integer( 7 ) ) );
       System.out.println( "======================================");
       System.out.println( "Search operation 1 : SEARCH ITEM 5 " );

       System.out.println( "Found 2 on index : " +
                                 binarySearch( a, new Integer( 2 ) ) );

    }

output :

binary search in Java
======================================
Search operation 1 : SEARCH ITEM 5
Lower val 0 Higher val 7
Mid val :3
Search Item : 5
Searching in lower half : 0
Lower val 4 Higher val 7
Mid val :5
Search Item : 5
Found 5 on index : 5
binary search in Java
======================================
Search operation 1 : SEARCH ITEM 5
Lower val 0 Higher val 7
Mid val :3
Search Item : 7
Searching in lower half : 0
Lower val 4 Higher val 7
Mid val :5
Search Item : 7
Searching in lower half : 4
Lower val 6 Higher val 7
Mid val :6
Search Item : 7
Searching in lower half : 6
Lower val 7 Higher val 7
Mid val :7
Search Item : 7
Found 7 on index : 7
binary search in Java
======================================
Search operation 1 : SEARCH ITEM 5
Lower val 0 Higher val 7
Mid val :3
Search Item : 2
Searching in upper half : 2
Lower val 0 Higher val 2
Mid val :1
Search Item : 2
Searching in lower half : 0
Lower val 2 Higher val 2
Mid val :2
Search Item : 2
Found 2 on index : 2


Summary of points in binary search in java :

1. Binary search in java done on sorted array.
2. Binary search in java is like half interval search.
3. Binary search in java is based on idea that element need to be searched in the middle. If found search ends. If element is greater than the middle element then search in upper half otherwise in lower half till search ends.
4. Performance in average case is 0 ( log n ), performance in best case is 0( 1 ).


Sources used for binary search in java
Share on Google Plus

About Pranav

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.
    Blogger Comment
    Facebook Comment

1 comments: