Binary Search
Binary search is a faster search algorithm when compared with the Lenier search. Binary search requires a sorted array (ascending order) to search an element init.
In Binary search, we jump into the middle of the array, where we find key a[mid], and compare x with a[mid]. If x = a[mid] then the desired record has been found.
- a = array of elements
- mid = middle point of an array
- x = element to 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 the further search is only necessary for that part of the file which follows a[mid].
If we use the 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;
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: 3Happy Learning 🙂
