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