Saturday, July 19, 2014

Binary Search Algorithm using Java

Binary search works faster than sequential search.It search on sorted elements.
In Binary Search, Let's say You have an array and you want to search specific item in array

How it Works :
  1. Initialize low=0 and high as max length of search array - 1.
  2. while low<=high each item you, take middle element of array and if given searchItem is less than middle element then you need to search in array of elements array which are less than middle element. Hence, high = middle - 1
  3. If given searchItem is larger than middle element then search in array of elements which are greater than middle element. Hence low = middle+1
  4. If searchItem == middle element then you have found your element.

Java Program for Binary Search Algorithm :
package com.anuj.algorithms;

import java.util.Arrays;

/**
 *
 * @author Anuj Patel
 * @source goldenpackagebyanuj.blogspot.com
 */
public class BinarySearch {

    public static void main(String[] args) {
        BinarySearch bs = new BinarySearch();
        int a[] = {1, 51, 3, 42, 5, 6, 17, 19, 12};
        int searchItem = 12;

        System.out.println("Before Sorting : " + Arrays.toString(a));
        Arrays.sort(a);
        System.out.println("After Sorting : " + Arrays.toString(a));
        System.out.println("Item being searched : " + searchItem);

        //int searchResult = Arrays.binarySearch(a, searchItem);
        int searchResult = bs.search(a, searchItem);
        System.out.println("The index of " + searchItem + " is : " + searchResult);
    }

    /**
     * Binary Search Algorithm
     *
     * @param a
     * @param searchItem
     * @return index of searchItem
     */
    public static int search(int[] a, int searchItem) {
        int low = 0;
        int high = a.length - 1;

        while (low &lt;= high) {
            int middle = (low + high) / 2;
            // int middle = (low+high) &gt;&gt;&gt; 1;
            int midVal = a[middle];

            if (searchItem &gt; midVal) {
                low = middle + 1;
            } else if (searchItem &lt; midVal) {
                high = middle - 1;
            } else {
                return middle;
            }
        }
        return -(low + 1); //Key not found
    }
}
Output :
run:
Before Sorting : [1, 51, 3, 42, 5, 6, 17, 19, 12]
After Sorting : [1, 3, 5, 6, 12, 17, 19, 42, 51]
Item being searched : 12
The index of 12 is : 4
BUILD SUCCESSFUL (total time: 0 seconds)

Author : Anuj Patel
Blog : http://goldenpackagebyanuj.blogspot.in/

No comments:

Post a Comment