Tuesday , February 28 2017
Home / Data Structures / Binary Search using Java

Binary Search using Java

If we have ‘n’ records which have been ordered by keys so that x 1 < x 2 < … < x n . When we are given a element ‘x’, binary search is used to find the corresponding element from the list. In case ‘x’ is present, we have to determine a value ‘j’ such that a[j] = x (successful search). If ‘x’ is not in the list then j is to set to zero (un successful search).

Binary Search

In Binary search we jump into the middle of the file, where we find key a[mid], and compare ‘x’ with a[mid]. If x = a[mid] then the desired record has been found. If x < a[mid] then ‘x’ must be in that portion of the file that precedes a[mid]. Similarly, if a[mid] > x, then further search is only necessary in that part of the file which follows a[mid].
If we use recursive procedure of finding the middle key a[mid] of the un-searched portion of a file, then every un-successful comparison of ‘x’ with a[mid] will eliminate roughly half the un-searched portion from consideration.
Since the array size is roughly halved after each comparison between ‘x’ and a[mid],
and since an array of length ‘n’ can be halved only about log 2 n times before reaching a
trivial length.

The worst case complexity of Binary search is about log 2 n.

Binary Search Algorithm

Let array a[n] of elements in increasing order, n ≥ 0, determine whether ‘x’ is present, and if so, set j such that x = a[j] else return 0.


binarySearch(a[], n, x)
{
            low = 1; high = n;
             while (low < high) do{
                        mid = ⎣ (low + high)/2 ⎦
                        if (x < a[mid])
                                    high = mid – 1;
                        else if (x > a[mid])
                                    low = mid + 1;
                        else return mid;
}
return 0;
}

low and high are integer variables such that each time through the loop either ‘x’ is found or low is increased by at least one or high is decreased by at least one. Thus we have two sequences of integers approaching each other and eventually low will become greater than high causing termination in a finite number of steps if ‘x’ is not present.

Binary Search Example


import java.util.Scanner;

/**
 *
 * @author chandrashekhar
 */
public class BinarySearch {

    public static void main(String[] args) {
        int a[];
        Scanner s = new Scanner(System.in);
        System.out.println("Enter  Size Of an Array");
        int n = s.nextInt();
        a = new int[n];
        System.out.println("Enter " + n + " Elements");
        for (int i = 0; i < n; i++) {
            a[i] = s.nextInt();
        }
        display(a);
        sort(a);
        display(a);
        System.out.println("Key To Find : ");
        int key = s.nextInt();
        int pos = binarySearch(a, 0, n-1, key);
        System.out.println("Element found @ position : "+pos);
    }

    public static void sort(int a[]) {
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < a.length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }

    public static int binarySearch(int a[], int low, int high, int key) {
        while (low <= high) {
            int mid = (low + high) / 2;
            if (a[mid] == key) {
                return mid;
            }
            if (key < a[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    public static void display(int a[]) {
        System.out.println("Array Elements Are");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
        System.out.println("");
    }
}

Output

Enter  Size Of an Array
5
Enter 5 Elements
20
30
50
80
40
Array Elements Are
20 30 50 80 40
Array Elements Are
20 30 40 50 80
Key To Find :
50
Element found @ position: 3

About chandrashekhar

Hi Folks, you have reach this so far, that shows you like what you are learning. Then why don't you support us to improve for bettor tutorials by leaving your valuable comments and why not you keep in touch with us for latest updates on your favorite blog @ facebook , twitter , Or Google+ ,

Check Also

What is an Algorithm ?

An algorithm is a finite sequence of instructions, each of which has a clear meaning …

Leave a Reply

Your email address will not be published. Required fields are marked *