Java Binary Search
Binary Search is an efficient search algorithm that is used to find a value in a sorted array. It performs a lot better than linear search. A normal linear search will not utilize the sorted array characteristics in any way, but a binary search uses the sorted array to eliminate one-half of the array in each iteration. In this tutorial, we will learn the binary search algorithm and implement it in Java.
Binary Search Algorithm
As discussed above, the binary search algorithm eliminates half of the array in each iteration. It does this by comparing the key(the value we are trying to search) to the middle element of the array.
- If the middle element is greater than the key, then all elements in the right half of the array will also be greater than the key because the array is sorted in ascending order.
- Similarly, if the middle element is smaller than the key then all elements in the left half will also be smaller.
- This way, in each comparison we have narrowed our search down to just half of the array.
We will use three index pointers to denote the leftmost index(starting of the array), rightmost index(ending of the array), and the middle index. The binary search algorithm is summarised in the following points.
- Compare the key to the middle element of the array. If the key matches the middle element, then return the index of the middle element.
- Else if the middle element is greater than the key, then the key can only be present in the left half. So we restart the search on the left half of the array. We reset the right index to the (middle index - 1).
- Else we restart the search on the right half of the array(because the middle element is smaller than the key). We reset the left index to the (middle index + 1).
- If the key is not present in the array then we return -1.
Binary Search - Dry Run
Let's try to understand how binary search works with the help of an example. Consider that we have the sorted array [5, 7, 15, 20, 110, 120, 139, 500] and we are trying to search the element 15 in it.
Initially, we will consider the entire array and the middle element of the array is 20.
15 is less than 20 so we will move to the left half. Now, the search will work on the array [5, 7, 15]. The middle element of this array will be 7.
15 is greater than 7 so we will move to the right half of the array [5, 7, 15]. The new array is [15]. The middle element of this array is 15.
15 is equal to the middle element(15) and so our search ends here.
Binary Search Implementation
The above algorithm can be implemented iteratively as well as recursively. We can use recursion here because, effectively, we are running the same three steps on different parts of the array. We will use the formula low + ((high - low) / 2) to calculate the middle index as it will avoid overflow for larger arrays.
Iterative Binary Search Implementation in Java
import java.util.Arrays;
public class BinarySearch
{
public static int binarySearchIterative(int[] sortedArray, int key)
{
int leftIdx = 0;
int rightIdx = sortedArray.length - 1;
while(leftIdx <= rightIdx)
{
int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
if(sortedArray[midIdx] == key)
return midIdx;
else if(sortedArray[midIdx] > key)
{
rightIdx = midIdx - 1;//left half of the array(from leftIdx to midIdx - 1)
}
else
leftIdx = midIdx + 1;//right half of the array(from midIdx + 1 to rightIdx)
}
return -1;//if key is absent
}
public static void main(String[] args)
{
int[] sortedArray = {5, 7, 15, 20, 110, 120, 139, 500};
int key1 = 139;
int key2 = 2;
System.out.println("The sorted list is: " + Arrays.toString(sortedArray));
System.out.println("The key " + key1 + " is present at index " + binarySearchIterative(sortedArray, key1));
System.out.println("The key " + key2 + " is present at index " + binarySearchIterative(sortedArray, key2));
}
}
The sorted list is: [5, 7, 15, 20, 110, 120, 139, 500]
The key 139 is present at index 6
The key 2 is present at index -1
Recursive Binary Search Implementation in Java
For the recursive method, we will pass the left extreme index and right extreme index to the method itself. For the initial call, the left index will be 0 and the right index will be one less than the length of the array.
import java.util.Arrays;
public class BinarySearch
{
public static int binarySearchRecursive(int[] sortedArray, int key, int leftIdx, int rightIdx)
{
if(leftIdx <= rightIdx)
{
int midIdx = leftIdx + (rightIdx - leftIdx) / 2;
if(sortedArray[midIdx] == key)
return midIdx;
else if(sortedArray[midIdx] > key)
{
return binarySearchRecursive(sortedArray, key, leftIdx, midIdx - 1); //left half of the array(from leftIdx to midIdx - 1)
}
else
return binarySearchRecursive(sortedArray, key, midIdx + 1, rightIdx);//right half of the array(from midIdx + 1 to rightIdx)
}
else
return -1;//if key is absent
}
public static void main(String[] args)
{
int[] sortedArray = {5, 7, 15, 20, 110, 120, 139, 500};
int leftIdx = 0;
int rightIdx = sortedArray.length - 1;
int key1 = 139;
int key2 = 2;
System.out.println("The sorted list is: " + Arrays.toString(sortedArray));
System.out.println("The key " + key1 + " is present at index " + binarySearchRecursive(sortedArray, key1, leftIdx, rightIdx));
System.out.println("The key " + key2 + " is present at index " + binarySearchRecursive(sortedArray, key2, leftIdx, rightIdx));
}
}
The sorted list is: [5, 7, 15, 20, 110, 120, 139, 500]
The key 139 is present at index 6
The key 2 is present at index -1
Using Inbuilt Methods for Binary Search
Arrays.binarySearch() Method in Java
The Arrays class in Java provides us a binarySearch() method that takes a sorted array and the key value to search as parameters and returns the index at which the key is present. It returns -1 if the key is not present in the array.
import java.util.Arrays;
public class BinarySearch
{
public static void main(String[] args)
{
int[] sortedArray = {5, 7, 15, 20, 110, 120, 139, 500};
int key1 = 139;
int key2 = 2;
System.out.println("The sorted array is: " + Arrays.toString(sortedArray));
System.out.println("The key " + key1 + " is present at index " + Arrays.binarySearch(sortedArray, key1));
System.out.println("The key " + key2 + " is present at index " + Arrays.binarySearch(sortedArray, key2));
}
}
The sorted array is: [5, 7, 15, 20, 110, 120, 139, 500]
The key 139 is present at index 6
The key 2 is present at index -1
Collections.binarySearch() Method in Java
The binarySearch() method of the Collections class can be used on collections like ArrayLists to search for an element. Just like the Arrays.binarySearch() method, it takes the sorted collection and a key as parameters and returns the index at which the key is present. It returns -1 if the key is absent from the list.
import java.util.ArrayList;
import java.util.Collections;
public class BinarySearch
{
public static void main(String[] args)
{
ArrayList<Integer> sortedList = new ArrayList<Integer>();
sortedList.add(5);
sortedList.add(7);
sortedList.add(15);
sortedList.add(20);
sortedList.add(110);
sortedList.add(120);
sortedList.add(139);
sortedList.add(500);
int key1 = 139;
int key2 = 2;
System.out.println("The sorted list is: " + sortedList);
System.out.println("The key " + key1 + " is present at index " + Collections.binarySearch(sortedList, key1));
System.out.println("The key " + key2 + " is present at index " + Collections.binarySearch(sortedList, key2));
}
}
The sorted list is: [5, 7, 15, 20, 110, 120, 139, 500]
The key 139 is present at index 6
The key 2 is present at index -1
Frequently Asked Questions
Q. Why is binary search called so?
Binary means composed of two things, and in binary search, we are just narrowing our search down to the two halves(left and right) in each iteration.
Q. Why can't we use binary search on unsorted arrays?
The binary search algorithm is based on sorted arrays. For unsorted arrays, there is no relation between the elements in the right or left half and the middle element. But for sorted arrays, we know that if the middle element is greater than a number then all elements in the right half will be greater than the element. Similarly, if the middle element is smaller than a number then all elements in the left half will also be smaller than the number.
Q. Does a Binary Search Tree use the Binary Search algorithm?
A binary search tree is created in such a way that all elements in the left sub tree are smaller than the root, and all elements in the right subtree are larger than the root. This makes the tree sorted and we can use the binary search algorithm to search a node in the tree.
Summary
Binary search is a fast and efficient way of searching for a value in a sorted array. Unlike the linear search that takes linear time(O(n)), the binary search takes logarithmic time(O(log(n)). The n denotes the total number of elements present in the array. The recursive implementation is easier to understand but recursion could be a bit slower because of the recursion stack.
Remember that binary search can only be used on a sorted array and if the array is not sorted then we should either use a sorting algorithm like merge sort to first sort the array or we can simply use linear search in that case. Using an additional sorting algorithm will increase the time complexity and linear search could be considered in such cases.
Overall, linear search performs better for arrays of smaller size whereas binary search is preferred for arrays of larger size.
