Introduction
In this article we are going to describe implementation of a Binary Search in the Java language. So first you should understand what a Binary Search is. A Binary Search is applicable only to a sorted array and any data structure.
Binary Search algorithm
Generally, to find a value in an unsorted array, we should look through elements of an array one by one, until the searched value is found. In the case that a searched value is absent from the array, we go through all the elements. On average, the complexity of such an algorithm is proportional to the length of the array.
The situation changes significantly, when an array is sorted. If we know it, the random access capability can be utilized very efficiently to find a searched value quickly. The cost of a searching algorithm reduces to the binary logarithm of the array length. For reference, log2(1 000 000) = 20. It means, that in the worst case, the algorithm requires 20 steps to find a value in a sorted array of a million elements or to say, that it doesn't access the entire array.
Algorithm
The following figure helps for a better understanding of the Binary Search concept:
![binary_search.gif]()
The algorithm is quite simple. It can be done either recursively or iteratively. The algorithm consists of the following steps:
Step 1: Get the middle element;
Step 2: If the middle element equals the searched value, the algorithm stops;
otherwise, two cases are possible:
Case 1: The searched value is less than the middle element. In this case, go to step 1 to search the half preceding the middle element.
Case 2: The searched value is greater than the middle element. In this case, go to step 1 to search the half following the middle element.
Step 3: Now we should define, when iterations should stop. First case is when searched element is found. Second one is when subarray has no elements. In that case we can conclude that the searched value is not present in the array.
Example
import java.util.*;
public class MyBinarySearch
{
public static void main(String[] args)
{
// this is a integer array with size 10
int[] a = new int[15];
int searchV = 0, index;
System.out.println("Enter 15 numbers");
//now we put all th value in a previous define array with help of scanner class
Scanner input = new Scanner(System.in);
for (int i = 0; i < a.length; i++)
{
a[i] = input.nextInt();
}
System.out.print("Enter a number to search for: ");
// take the user input which he want to search
searchV = input.nextInt();
index = binarySearch(a, searchV);
if (index != -1)
{
System.out.println("Found at index: " + index);
}
else
{
System.out.println("Not Found");
}
}
// here we define binary search method
static int binarySearch(int[] search, int find)
{
int start, end, midPt;
start = 0;
end = search.length - 1;
while (start <= end)
{
midPt = (start + end) / 2;
if (search[midPt] == find)
{
return midPt;
}
else if (search[midPt] < find)
{
start = midPt + 1;
}
else
{
end = midPt - 1;
}
}
return -1;
}
}
Output
![binarysearch.jpg]()
Resources
Binary Search Using ArrayList
Sorting, Searching and some other useful programs
Use of ByteStreams and CharacterStreams in JAVA
Learning JDBC (Java Database Connectivity)
Working with Hibernate - Display , Insert, Update and Delete in JAVA