Binary Search In Java with Examples - An Interview Guide
Introduction to Binary Search:-
Searching is one of the most rudimentary tasks that almost all of us perform on a daily basis, be it searching for phone numbers on our mobile phones or searching for books on our shelves. Searching has an important role in most fields of study that exist today and Computer Science is no different. Tonnes of problems in Computer Science require the usage of some sort of searching algorithm and therefore, coming up with a fast algorithm for searching is absolutely critical. In Computer Science, a number of searching algorithms have been discovered, for example:-
1)Linear Search
2)Binary Search
3)Ternary Search
4)Interpolation Search
All these searching algorithms are put into use according to the requirements of the problem. Among these, one of the most powerful search algorithms is the BINARY SEARCH ALGORITHM, because the time complexity of binary search is O(log(N)),where N stands for the size of the search space. The time complexity of Binary Search is what makes it better than other searching algorithms like Linear Search(Linear search has a time complexity of O(N)),etc. However, in order to apply the binary search algorithm, certain conditions need to be satisfied. We will learn about them in a later section of this article.
Formal Problem Statement:-
We can formally define the problem of searching as follows:-
Given a list of N elements, we need to find whether the element X is present in the given list or not.
Here, the given list can be of any data type - integers, strings, decimal values, objects,etc
Linear Search Algorithm:-
Now that we have defined the problem statement formally,let us look at an elementary approach to solve the given problem - Linear Search Algorithm. In Linear Search, we simply traverse the given list and compare each element of the list to the element to be searched - X. If we find X in the list, we can terminate our linear search.
Time Complexity Of Linear Search Algorithm : In the worst case scenario, that is, the scenario in which X is present at the opposite end of the list from where we started our search or X is not present at all in the list,all the elements of the list are traversed and hence the time complexity of linear search algorithm in the worst case is O(N).
Note: The order of the list elements and the type of the given list(whether it is an array, linked list, etc) does not matter in Linear Search Algorithm.
Prerequisites For Binary Search Algorithm:-
A question that all Computer Science enthusiasts ask very frequently when they come up with solutions to a problem is - Can we do better?Well,the searching problem was no different to them.
The Binary Search Algorithm is a major improvement over the Linear Search Algorithm if the following prerequisites are met:-
1)The given list should be sorted, either in Ascending or in Descending order.
2)The given list should support constant time, that is, O(1) time element access operations. Hence, while binary search can be applied on sorted arrays, it cannot be applied on sorted linked lists.
What is Binary Search?:-
The Binary Search Algorithm is based on the Algorithmic paradigm - DIVIDE AND CONQUER.
The Divide and Conquer technique consists of the following three steps:-
1)DIVIDE- The first step of this paradigm involves breaking down the given problem into a number of subproblems, which are smaller instances of the original problem.
2)CONQUER - This step involves further break down of the smaller problems into subproblems until the size of the subproblems become very small. After that the subproblems are solved in a straightforward manner.
3)COMBINE - The third and final step of the Divide and Conquer paradigm involves combining the solutions of the subproblems into the solution of the original problem.
In Binary Search, the search space of the problem is halved at each step by comparing the value of the element to be searched with the middle element of the current search space. The binary search algorithm consists of the following steps:-
STEP 1: Let ‘l’ denote the left-most index of the given list and ‘r’ denote the right-most index of the given list. Let the given list be denoted by A and let us assume that A is sorted in ascending order and the access time for elements at a particular index is constant, i.e., O(1).
STEP 2 : The index of the middle element - ‘mid’ - of the current search space is found out using the following formula:-
mid = l+((r-l)/2)
STEP 3 : The middle element of the current search space - A[mid] - is then compared to the element to be searched(X).The following three scenarios can occur:-
(i) If A[mid] is equal to X, we terminate our search and return the index ‘mid’.
(ii) if A[mid] is greater than X, we know that all elements to the right of the index ‘mid’ will be greater than X (as the list is sorted in ascending order) and therefore, as there is no point of searching for X on the right side of ‘mid’, we reduce the search space to half by making the right-end of the search space equal to mid-1:-
r = mid-1
(iii) if A[mid] is smaller than X, we know that all elements to the left of the index ‘mid’ will be smaller than X (as the list is sorted in ascending order) and therefore, as there is no point of searching for X on the left side of ‘mid’,we reduce the search space to half by making the left-end of the search space equal to mid+1:-
l = mid+1
STEP 4 : If the left end index ‘l’ is smaller than the right end index ‘r’, we repeat steps 2 - 4.If not, then we can terminate our search and say for sure that the element X is not present in the list A.
BINARY SEARCH FLOWCHART
Time Complexity Of Binary Search Algorithm :-
In each step of the binary search algorithm,we reduce the search space to half.Hence,we can write the recurrence relation of the time complexity of binary search as follows:-
T(N) = T(N/2) + C
(Here N is the size of the search space and C denotes the constant time taken.)
The above recurrence relation can be solved using Master’s Theorem and the solution to it comes out to be
O(log(N)).Hence the time complexity of the binary search algorithm is logarithmic.
Space Complexity Of Binary Search Algorithm:-
For an iterative version of the binary search algorithm,the space complexity is constant - O(1).
For a recursive version of the binary search algorithm,the space complexity is logarithmic - O(log(N)) because of the recursion call stack space.
Binary Search In JAVA:-
Now that we have understood what is Binary Search and how it works, let us get our hands dirty and dive deep into the code of the Binary Search in Java:-
(1)Recursive implementation of Binary Search In Java:-
{
//Binary Search in Java - RECURSIVE Implementation
class BinarySearchRecursive {
/*This function returns the index(0 based indexing is used) of the array 'A' where the element 'X' is present.
If 'X' is not present in A,this function returns -1 */
int binarySearch(int A[], int l, int r, int X)
{
if (l <= r) {
//mid stores the middle element of the current search space
int mid = l + ((r - l) / 2);
//If the middle element of the current search space is equal to X,we return the index - mid
if (A[mid] == X)
return mid;
/*If the middle element of the current search space is greater than X,we can ignore the elements to
the right of mid as all of them will be greater than X.Hence we can make the right boundary equal to
mid-1 and recur in the range l to mid-1 */
if (A[mid] > X)
return binarySearch(A, l, mid - 1, X);
/*If the middle element of the current search space is smaller than X,we can ignore the elements to
the left of mid as all of them will be smaller than X.Hence we can make the left boundary equal to
mid+1 and recur in the range mid+1 to r */
return binarySearch(A, mid + 1, r, X);
}
/*if the value of the left boundary exceeds the value of the right boundary,element X was not present
in the given array.So we return -1 */
return -1;
}
//main method of the BinarySearchRecursive class
public static void main(String args[])
{
BinarySearchRecursive bin = new BinarySearchRecursive ();
int A[] = { 1, 12, 23, 24, 30, 60, 223, 555 }; //the given sorted list
int len = A.length;//stores the length of A
int X = 30; //the element to be searched
int solutionIndex = bin.binarySearch(A, 0, len - 1, X);
//apply binary search to find the index of X in A.
if (solutionIndex == -1)
System.out.println("Element " + X + " is not present in the given array!");
else
System.out.println("Element " + X + " was found at index " + solutionIndex + " of the given array!");
}
}
(2)Iterative implementation of Binary Search In Java:-
class BinarySearchIterative {
/*This function returns the index(0 based indexing is used) of the array 'A' where the element 'X' is present.
If 'X' is not present in A,this function returns -1 */
int binarySearch(int A[], int len, int X)
{
int l = 0,r = len-1;
while (l <= r) {
//mid stores the middle element of the current search space
int mid = l + ((r - l) / 2);
//If the middle element of the current search space is equal to X,we return the index - mid
if (A[mid] == X) {
return mid;
}
/*If the middle element of the current search space is greater than X,we can ignore the elements to
the right of mid as all of them will be greater than X.Hence we can make the right boundary equal to
mid-1 and iterate in the range l to mid-1 */
else if (A[mid] > X) {
r = mid - 1;
}
/*If the middle element of the current search space is smaller than X,we can ignore the elements to
the left of mid as all of them will be smaller than X.Hence we can make the left boundary equal to
mid+1 and iterate in the range mid+1 to r */
else {
l = mid+1;
}
}
/*if the value of the left boundary exceeds the value of the right boundary,element X was not present
in the given array.So we return -1 */
return -1;
}
//main method of the BinarySearchIterative class
public static void main(String args[])
{
BinarySearchIterative bin = new BinarySearchIterative ();
int A[] = { 1, 12, 23, 24, 30, 60, 223, 555 }; //the given sorted list
int len = A.length;//stores the length of A
int X = 30; //the element to be searched
int solutionIndex = bin.binarySearch(A ,len , X);
//apply binary search to find the index of X in A.
if (solutionIndex == -1)
System.out.println("Element " + X + " is not present in the given array!");
else
System.out.println("Element " + X + " was found at index " + solutionIndex + " of the given array!");
}
}
(3)Binary Search In Java using Arrays.binarySearch() Method:-
import java.util.*;
//Binary Search in Java - using binarySearch() method in Arrays.util library
class binarySearchMethod {
//main method of the binarySearchMethod class
public static void main(String args[])
{
int A[] = { 1, 12, 23, 24, 30, 60, 223, 555 }; //the given sorted list
int len = A.length;//stores the length of A
int X = 30; //the element to be searched
int solutionIndex = Arrays.binarySearch(A, X);
//apply binary search to find the index of X in A.
if (solutionIndex < 0)
System.out.println("Element " + X + " is not present in the given array!");
else
System.out.println("Element " + X + " was found at index " + solutionIndex + " of the given array!");
}
}
Conclusion : How to use Binary Search in Coding Interviews?:-
Here are a few resources and tips on what type of binary search questions could be asked in coding interviews:-
(1)The biggest hint for the usage of binary search on an array is the fact that the array is sorted or the array can be sorted and then an optimal answer can be arrived at. So, one should ask the interviewer questions regarding the order of the array elements, size of the array, etc.
(2)If we can conclude that a given function in the question is monotonic,that is,the function increases or decreases monotonically with the increase in the value of some variable,then applying binary search can be very useful.
(3)While Binary Search is an extremely powerful algorithm, questions where the time complexity doesn’t matter as much and questions, for which, linear search will suffice,using binary search can be an overkill.
For instance,if the time complexity of our current solution is already O(Nlog(N)) or O(N) or O(1),usage of binary search will only make the code more complex.Therefore, the usage of binary search is advised only if our current time complexity is O(N^2) or more.
Resources:
Introduction to Binary Search: Link
Binary Search in Java Tutorial: Link
Java Interview Questions: Link
