Binary Search

Binary search is a method to find the particular item in the sorted array. In each step, the algorithm divides the array equally and match the middle item. If the key match, return the index. If the key is less than the middle element, search left subarray. Else search right subarray.

Binary search uses divide and conquers strategy to search the item from the sorted array. The binary search eliminates half of the elements for each iteration. It requires sorted array and will not work for the un-sorted array like linear search.

The binary search algorithm can be implemented using an iterative method or recursive method. Write a program to implement Binary search.

source Code

package com.dsacode.Algorithm.search;
 
import java.util.Arrays;
 
public class BinarySearch {
    public static int BinSearch(int a[], int low, int high, int x){
        int mid = (low+high)/2;
        if(a[mid] == x)
            return mid;
        else if(a[mid] > x)
            return BinSearch(a,low,mid-1,x);
        else
            return BinSearch(a,mid+1,high,x);
    }
 
    public static int Binarysearch(int a[], int x){
        int low = 0, high = a.length -1;
        int mid = 0;
        while(low <= high){
            mid = (low + high)/2;
             
            if(a[mid] > x)
                high = mid-1;
            else if(a[mid] < x)
                low = mid+1;
            else
                return mid;
        }
        return -1;
    }
     
    public static void main(String[] args) {
        int[] array = {12, 55, 45, 11, 23, 20, 17, 24, 9};
        System.out.println("Before Sort:" + Arrays.toString(array));
        Arrays.sort(array);
        System.out.println("After Sort:" + Arrays.toString(array));
         int pos = -1;
         if( (pos= Binarysearch(array,11)) == -1)
             System.out.println("Not found!");
         else
             System.out.println("Found in " + (pos+1) + " Position!");
 
    }
}

Output

Before Sort: [12, 55, 45, 11, 23, 20, 17, 24, 9]
After Sort: [9, 11, 12, 17, 20, 23, 24, 45, 55]
Found in 2 Position!

Algorithm Explanation

	The binary search starts from the beginning of the array to end of the array.
	The algorithm divides an array equally and matches the middle item with the search key.
	If the key matches with middle item, it returns the position
	If the key less than the middle item, it searches from the first half of the array.
	If the key greater teen middle item, it searches from the second half of the array.

Time Complexity

Reference

1. http://en.wikipedia.org/wiki/Binary_search_algorithm
2. https://www.topcoder.com/community/data-science/data-science-tutorials/binary-search