Binary Search
In this approach, the given array must be sorted either in Ascending or Descending Order.
It always check the middle element of the array or sub-array to apply the search. If not
found on the middle element then either it search in Lower Half (Left Side) or Upper Half
(Right Side).
( 𝐵𝐸𝐺 + 𝐸𝑁𝐷 )
Formula to find the MIDDLE Element Index No =
2
Here Initially, BEG = 0 and END = ARR.length - 1
Given :
1. Sorted Array in which search to be applied (ARR)
2. Value to be Searched (REQ)
Output Required :
First Index Location where the searched value is found otherwise
return -1 or Display Appropriate Message
Example No 1 : Value to be Searched (REQ) : 41
9 12 35 41 78 82 95
0 1 2 3 4 5 6
----------------------------------------------------------------------------------------------------------------------
BEG MID END
Found
(Search Over)
Search Status : 41 found at Index No : 3
Dry Run :
REQ BEG END MID Condition Search Status
Found at MID location
41 0 6 3 REQ == ARR[ MID ]
( Search Over )
Example No 2 : Value to be Searched (REQ) : 82
9 12 35 41 78 82 95
0 1 2 3 4 5 6
----------------------------------------------------------------------------------------------------------------------
BEG MID END
----------------------------------------------
BEG MID END
Found
(Search Over)
Search Status : 82 found at Index No : 5
Dry Run :
REQ BEG END MID Condition Search Status
82 0 6 3 REQ > ARR[ MID ] i.e. 82 > 41 Now, search in Upper Half
Found at MID location
4 6 5 REQ == ARR[ MID ]
( Search Over )
Example No 3 : Value to be Searched (REQ) : 35
9 12 35 41 78 82 95
0 1 2 3 4 5 6
----------------------------------------------------------------------------------------------------------------------
BEG MID END
----------------------------------------------
BEG MID END
----------
BEG
END
MID
Found
(Search Over)
Search Status : 35 found at Index No : 2
Dry Run :
REQ BEG END MID Condition Search Status
35 0 6 3 REQ < ARR[ MID ] i.e. 35 < 41 Now, search in Lower Half
0 2 1 REQ > ARR[ MID ] i.e. 35 > 12 Now, search in Upper Half
Found at MID location
2 2 2 REQ == ARR[ MID ]
( Search Over )
Example No 4 : Value to be Searched (REQ) : 80
9 12 35 41 78 82 95
0 1 2 3 4 5 6
----------------------------------------------------------------------------------------------------------------------
BEG MID END
----------------------------------------------
BEG MID END
----------
BEG
END
MID
END BEG
Not Found
(Search Over)
Search Status : 80 Not found
( Here, when BEG > END then Search is Over… Value not found )
Dry Run :
REQ BEG END MID Condition Search Status
80 0 6 3 REQ > ARR[ MID ] i.e. 80 > 41 Now, search in Upper Half
4 6 5 REQ < ARR[ MID ] i.e. 80 < 82 Now, search in Lower Half
4 4 4 REQ > ARR[ MID ] i.e. 80 > 78 Now, search in Upper Half
NOT Found
5 4 when BEG > END then Search is Over
( Search Over )
Binary Search Program which works for any Primitive Data Type
( Solved with 1D Array of int )
import java.util.*;
class BinarySearch_Scanner_int
{
public static void main( )
{
Scanner SC = new Scanner( System.in );
System.out.print( " Enter the No of Elements required : " );
int SIZE = SC.nextInt( );
int [ ] ARR = new int[ SIZE ] ;
int K ;
System.out.println( " Enter the Integer values for an Array in Ascending Order: " );
for( K = 0 ; K < ARR.length ; K++ )
{
System.out.print( "\t Enter the value for ARR[ " + K + " ] : " );
ARR[K] = SC.nextInt( );
}
System.out.print( " Enter the value to be searched : " );
int REQ = SC.nextInt( );
System.out.println( "\n Given values are : " );
for( K = 0 ; K < ARR.length ; K ++ )
{
System.out.print( "\t" + ARR[K] );
}
// ---- Binary Search Code ( which works for any Primitive Data Type )---
int beg, end, mid;
beg = 0;
end = ARR.length - 1;
mid = -1 ;
while( beg <= end ) // for ( ; beg <= end ; )
{
mid = ( beg + end ) / 2 ;
if( REQ == ARR[mid] ) // found
break;
if( REQ > ARR[mid] ) // REQ value to be searched in Upper Half
beg = mid + 1;
else // REQ value to be searched in Lower Half
end = mid - 1;
} // end of while loop
System.out.print( "\n\n Search Status : " );
if( beg > end )
System.out.println( "\t" + REQ + " not found !!! " );
else
System.out.println( "\t" + REQ + " found at index no. : " + mid );
} // end of main
} // end of class
Binary Search Program which works for String Data Type
( Solved with 1D Array of String )
import java.util.*;
public class BinarySearch_Scanner_String
{
public static void main( int SIZE )
{
Scanner SC = new Scanner( System.in );
String [ ] NAMES = new String[ SIZE ] ;
int K ;
System.out.println( " Enter the Names for an Array in Ascending Order: " );
for( K = 0 ; K < NAMES.length ; K++ )
{
System.out.print( "\t Enter the any name for NAMES[ " + K + " ] : " );
NAMES[K] = SC.nextLine( ).toUpperCase( );
}
System.out.print( " Enter the name to be searched : " );
String REQ = SC.nextLine( ).toUpperCase( );
System.out.println( "\n Given Names are : " );
for( K = 0 ; K < NAMES.length ; K ++ )
{
System.out.print( "\t" + NAMES[K] );
}
// Binary Search code ( for String Array )
int beg, end, mid, N;
beg = 0;
end = NAMES.length - 1;
mid = -99 ;
while( beg <= end )
{
mid = ( beg + end ) / 2 ;
N = REQ . compareTo ( NAMES[mid] );
if( N == 0 ) // Both strings are same
break;
if( N > 0 ) // REQ value to be searched in Upper Half
beg = mid + 1;
else
end = mid - 1;
} // end of while loop
System.out.print( "\n\n Search Status : " );
if( beg > end )
System.out.println( "\t" + REQ + " not found !!! " );
else
System.out.println( "\t" + REQ + " found at index no. : " + mid );
} // end of main
} // end of class
