Overview
In this tutorial, we will write a Java program to implement Binary Search. BS is faster than sequential search. The requirement for BS is that the array should be sorted in a particular order before searching.
Divide and Conquer
Assume that searchItem that needs to be searched and array sorted in ascending order. We will find the middle of the array and compare with searchItem.
If searchItem is greater than the middle item of the array then search the right half of the array. If the searchItem is less than the middle item, then search the left half array.
Flow Chart
Binary Search Java program
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Scanner;
public class BinarySearchExample {
public static void main(String[] args) {
int n;
Scanner input = null;
int[] a = null;
int searchItem,low,high;
try {
input=new Scanner(System.in);
System.out.println("Enter size of the array:");
n= input.nextInt();
if(n > 0) {
a=new int[n];
System.out.println("Enter array elements:");
for (int i = 0; i < n; i++) {
a[i] = input.nextInt();
}
}else{
System.out.println("Enter positive number.");
System.exit(0);
}
System.out.println("Input Unsorted Array is:");
printArray(a);
System.out.println("Enter the search item");
searchItem =input.nextInt();
Arrays.sort(a);
System.out.println("Input Sorted Array is:");
printArray(a);
System.out.println("Performing Binary search for:"+ searchItem);
low=0;
high=a.length-1;
while(high >= low) {
int mid = (high+low)/2;
if(a[mid] == searchItem){
System.out.println("Item found at:" + mid );
System.exit(0);
}
else if(a[mid] < searchItem) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
}catch (InputMismatchException ime) {
System.out.println("Not a valid input");
}
catch (Exception e) {
e.printStackTrace();
} finally
{
if(input!=null)
{input.close();}
}
}
private static void printArray(int[] a){
for (int aA : a) {
System.out.print("[ " + aA + " ]");
}
System.out.println( "");
}
}
Run output of the program
Save the program in the IDE and execute the program.
User Input for the program:
Enter the size of the array. The program prompts for array elements. Enter the array elements.
The program then prompts the user to enter the search item.
Enter size of the array:
7
Enter array elements:
23
56
9
103
77
99
14
Input Unsorted Array is:
[ 23 ][ 56 ][ 9 ][ 103 ][ 77 ][ 99 ][ 14 ]
Enter the search item
77
Input Sorted Array is:
[ 9 ][ 14 ][ 23 ][ 56 ][ 77 ][ 99 ][ 103 ]
Performing Binary search for:77
Item found at:4
—
Java Tutorial on this website: https://www.testingdocs.com/java-tutorial/
For more information on Java, visit the official website :
https://www.oracle.com/in/java/