In this quick tutorial, we’ll learn to perform a binary search in a sorted array. We’ll also write our own algorithmic implementation in Java. Later, we’ll discuss the binarySearch() method available in the Java library.
Let’s say we have a sorted array a[]:
int[] a = {1, 2, 3, 4, 5, 6};
We as developers always ask: ‘Can we do better?’
The answer here is yes. We’ll use the binary search algorithm to do so.
Binary search is a decrease-and-conquer algorithm i.e. it reduces the problem domain to half in each iteration till we have it solved. The algorithm has the following steps:
Let’s implement it in Java:
int binarySearch(int[] a, int n, int x) { int low = 0, high = n-1; while(low <= high) { int mid = low + (high-low)/2; if(a[mid] == x) return mid; else if(x > a[mid]) low = mid + 1; else high = mid - 1; } //element x not found return -1; }
Please note that we’ll have an unpredictable output if the array is unsorted.
Implementing binary search algorithm recursively is also pretty straightforward. So, our recursive algorithm implementation in Java would look like:
int binarySearch(int a[], int low, int high, int x) { if(low > high) return -1; int mid = low + (high - low)/2; if(a[mid] == x) return mid; else if(x < a[mid]) return binarySearch(a, low, mid - 1, x); else return binarySearch(a, mid + 1, high, x); }
int index = binarySearch(a, 0, a.length - 1, 5);
Having looked at how to implement a binary search algorithm, let’s discuss the helper method available in our java.util.Arrays class in Java:
//x being the element we're looking for int index = Arrays.binarySearch(a, x);
So, for example:
int[] a = {1, 2, 3, 4, 6, 7}; int indexOf4 = Arrays.binarySearch(a, 4); // indexOf4 = 3 int indexOf5 = Arrays.binarySearch(a, 5); // indexOf5 = -5
Similar to Arrays.binarySearch(), we also have a method binarySearch() in our Collections class in Java. It helps us perform a binary search on some form of a Collection like an ArrayList or a LinkedList:
List<Integer> list = new ArrayList(); list.add(1); list.add(2); list.add(4); int indexOf2 = Collections.binarySearch(list, 2); // indexOf2 = 1
In this tutorial, we looked at the iterative as well as the recursive solution to implement the binary search algorithm in Java. We also discussed the Arrays.binarySearch() and Collections.binarySearch() utilities available in our Java library.