What is Binary Search?

Binary Search is a commonly used searching technique in Java that involves searching an already sorted array. This process supersedes the Linear Search as it is a more effective solution and significantly reduces the time complexity.

Algorithm

As the array is sorted, Binary Search determines a middle element of the array and uses it as a pivot for the following steps:

1. The middle element is checked to match the element being searched for. Upon a successful match, this element is returned.
2. If not, the array is broken into two parts. If the element being searched for is greater than the middle element, only the right part of the array is searched and vice versa.
3. If the element is not present, return -1, and display an appropriate message.

Example and Code

// The Iteration Method is illustrated here. Recursion can also be used to perform the same function.
class BinarySearch {
int binarySearch(int arr[], int x)
{
int l = 0, r = arr.length - 1;
while (l <= r)
{
int m = l + (r - l) / 2;
// To check whether the middle element is the one being searched
if (arr[m] == x) return m;
// If x greater, we only search the right half of the array
if (arr[m] < x) l = m + 1;
// If x is smaller, we only search the left half of the array
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}

public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = { 1, 4, 8, 90, 100, 150, 160 };
int n = arr.length;
int x = 100;
int result = ob.binarySearch(arr, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index: " + result);
}
}

OUTPUT

Element found at index: 4

Complexity

The Time Complexity of Binary Search is O(log n). This comes from the original equation T(n) = T(n/2) + c. There are various ways to derive the solution to the equation. Methods like the Recurrence Tree or Master can be used easily.