Java Program to implement binary search


May 6, 2022, Learn eTutorial
1447

Here we are explaining how to write a java program to perform a binary search.

What is binary search in java?

Binary search is implemented on a sorted array. The list should be sorted in ascending order. The logic of binary search is, check the key element is less than the middle element or not. If true then we will discard the middle+1 to limit portion and continue the searching process from 1 to middle-1 element. If the key element = middle element then we will display the element is found at the position middle.

How to implement the java program to perform a binary search?

First, we have to declare the class BinarySerach.Declare the integer variables i,limit,key,first,last,middle.Create an object of the scanner class as sc. Read the limit of the array elements as a limit. Declare an integer array of size limit. Read the array elements using a for loop into array[i]. Read the search element into the key.Then set first=0.last=lmit-1,middle=first+last/2.Then By using a while loop we will check the array[middle] is less than the key, if the middle element is smaller than the key element then we will continue the searching process from middle + 1 to last. Else we continue the search process from first to middle -1.If the array[middle]=key,then display the element is found at middle+1 position.If first > last, the display key is not found.

 

ALGORITHM

STEP 1: Declare the class BinarySearch with a public modifier.

STEP 2: Open the main() to start the program, Java program execution starts with the main()

STEP 3: Declare the integer variables i,limit,key,first,last,middle.

STEP 4: Read the limit of the array into the variable limit.

STEP 5: Declare an array of size limit.

STEP 6: Read the elements into the array by using for loop.

STEP 7: Read the element which is to be searched into the variable key.

STEP 8: Set flag=0,last=limit-1,calculate middle as (first+last)/2.

STEP 9: By using a while loop with the condition first <= last  do step 10

STEP 10:Check if array[middle] < key, then set first =middle +1.

STEP 11:Else check if array[middle]==key, then display the key element is found at the position as middle +1.

STEP 12: Else set  last= middle -1.

STEP 13:calculate middle=first+last/2 and repeat step 9.

STEP 14:If first >  last then display key is not found.

 

Java Source Code

                                          import java.util.Scanner;
public class BinarySerach{
   public static void main(String args[]){
      int i, limit,key,first, last, middle;
      Scanner sc = new Scanner(System.in);
      System.out.println("Enter the limit of numbers:");
      limit = sc.nextInt(); 

      int array[] = new int[limit];

      System.out.println("Enter " + limit + " numbers");
      for (i= 0; i < limit; i++)
          array[i] = sc.nextInt();

      System.out.println("Enter the search element:");
      key= sc.nextInt();
      first = 0;
      last = limit - 1;
      middle = (first + last)/2;

      while( first <= last )
      {
         if ( array[middle] < key )
           first = middle + 1;
         else if ( array[middle] == key )
         {
           System.out.println("The key element "+key +" found at location "+(middle+1)); 
           break;
         }
         else
         {
             last = middle - 1;
         }
         middle = (first + last)/2;
      }
      if ( first > last )
          System.out.println(key + " is not found.\n");
   }
}
                                      

OUTPUT

Enter the limit of numbers:5
Enter 5 numbers:
2 
6
8
10
12
Enter the search element:12
The key element 12 found at location 5