Tuesday, 6 January 2015

Java Program to search an element using Binary Search Technique


In this post we will discuss on a basic searching technique called as binary search . It searches an element (generally called a key ) from a sorted array.

The array is divided into 2 sub arrays one from middle to start and other sub array from middle to end. If the sorted array is in ascending order and the key element is greater than the middle it searches the right sub array else left sub array  and the same process continues in those sub arrays until the key element is found.

PROGRAM :
package codingcorner.in;

import java.util.Scanner;

public class BinarySearch {
 public static void main(String[] args) {

  int i, first, last, middle, n, key;
  int[] array = new int[100];

  Scanner scan = new Scanner(System.in);

  System.out.print("How many elements ?\t");
  n = scan.nextInt();

  for (i = 0; i < n; i++) {
   System.out.print("Enter number " + (i + 1) + ":\t");
   array[i] = scan.nextInt();
  }

  System.out.print("\nEnter value to find\t");
  key = scan.nextInt();

  scan.close();

  first = 0;
  last = n - 1;
  middle = (first + last) / 2;

  while (first <= last) {
   if (array[middle] < key)
    first = middle + 1;
   else if (array[middle] == key) {
    System.out.println(key + " found at position" + (middle + 1)
      + "\t");
    break;
   } else
    last = middle - 1;

   middle = (first + last) / 2;
  }
  if (first > last)
   System.out.println("Not found!" + key
     + " is not present in the list.\n");
 }
}

OUTPUT :