Divide and conquer

Binary search

Pinterest LinkedIn Tumblr

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

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

The binary search algorithm can be implemented using the iterative method and 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

Search start from beginning of the array to end of the array.
In each step, the algorithm divides the array equally and match the middle item with the search key.
If the key matches middle item, it returns the position.
If the key less than middle item, it searches from first half of the array.
If the key greater than the middle item, it searches from the second half of the array.

Time Complexity

Best CaseAverage CaseWorst Case
O(1)O(log n)O(log n)

Reference

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

1 Comment

  1. Welll written and done.
    I started writing myself in the last few days and have seen
    lot of writers merelyy rework old content but aadd very little of benefit.
    It’s greeat to see a helpful article of some actual
    value to your followers andd myself.
    It is going onn the list of factors I need to emkulate being a nnew blogger.
    Visitor engagement and content quality are king.
    Many fantastic thoughts; you’ve absolutely managed to get oon my listt of blogs
    to watch!

    Carry on the excellent work!
    Congratulations,
    Dody

Write A Comment