Sunday, April 27, 2014

Binary Search-Sample program in Java

What is Binary Search by the way?

A binary search or half-interval search algorithm finds the position of a specified input value (the search "key") within an array sorted by key value.[1][2] For binary search, the array should be arranged in ascending or descending order. In each step, the algorithm compares the search key value with the key value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. If the remaining array to be searched is empty, then the key cannot be found in the array and a special "not found" indication is returned.
(Source: WikiPedia)

The requirement for binary search algo is the array should be sorted.We can use Quick Sort or Merge Sort for sorting the array.First we need to take mid element(if low=0 and high=array.length-1 then mid=low+high/2).If the middle element is the one which we are searching we return the index or we just print the element is found in the array at a specified index.

Lets say the element we are searching is less than the middle element then we will take the sub array by specifying high=mid-1 or if the searching element is greater than the middle element then our sub array becomes low=mid+1.This process will continue until we found the element we are searching.

Code:

/**
 * @author RameshM
 * 
 *         Sample program for Binary Search
 */
public class BinarySearchTest {

 public static boolean searchKey(int[] intArray, int element) {

  int low = 0;
  int high = intArray.length - 1;

  while (low <= high) {
   int middle = (low + high) / 2;
   if (element > intArray[middle]) {
    low = middle + 1;
   } else if (element < intArray[middle]) {
    high = middle - 1;
   } else {
    return true;
   }
  }
  return false;
 }

 public static void main(String args[]) {

  int[] intArray = { 2, 4, 5, 8, 9, 22, 44, 55, 66, 88, 100 };

  int element = 44;

  boolean result = searchKey(intArray, element);

  if (result) {
   System.out.println("The element found in the Array");
  } else {
   System.out.println("The element is not found in the Array");
  }

 }
}

Output:

The element found in the Array