Binary Search Explanation & Related Problems-Java
Suppose we want to search for a particular element in an array of ’n’ elements and return its index if it exists or return -1 if it doesn’t exist.
We can traverse through the entire array till we find the element and return the index at which the element is found. If the element is not found in the entire array, return -1. This is “Linear Search”. Since we may have to traverse through all the ’n’ elements in the worst case, the time complexity of the linear search algorithm is : O(n). Big-O represents the upper bound of the time complexity.
Can we do better? What if the array is sorted?
Imagine you are looking for a word in a dictionary. We know that all the words in the dictionary are arranged in chronological order. We randomly open the dictionary. If we are on a page with words that come later than our desired word in the chronological order, we move to the front pages from the current page. If we are close to the desired word, we’ll keep looking on the same page. If we are on a page with words that come before our desired word, we move to the next pages from the current page and keep doing this till our word is found.
Binary Search works exactly in the same way. It uses the same intuition and translates it into an algorithm. Note that it can be applied only on sorted arrays.
If you look at the above diagram, we are starting with the middle element of the array. We compare the desired element with the middle element. If the desired element is greater than the middle element, we completely ignore the first half and continue searching in the same way in the second half. Because you can’t find the desired element in the first half as the array is sorted.
Now when we are searching the second half, we pick the middle element of the second half and keep doing this till at some point the desired element is same as the middle element.
So how are we going to implement this algorithm?
Suppose we have pointers start and end which represent the start index and end index of the selected portion of the array. Initially we want to consider the entire array so, start = 0 and end = array.length-1. To get the index of the middle element we can do (start + end) / 2. But there are some downsides to finding the middle element using this formula. You can check out the reasons here.
We need to stop the search when start is no longer less than or equal to end. Because by the time we meet this condition, we would have already searched relevant parts of the array.
That sums up our algorithm to:
int binarySearch(int[] arr, int target) {
int start = 0, end = arr.length - 1;
while(start <= end) {
int mid = start + (end - start) / 2;
if(arr[mid] == target) return mid;
else if(arr[mid] > target) end = mid - 1;
else start = mid + 1;
}
return -1;
}void testBinarySearch() {
int[] arr = new int[]{1,3,5,23,33,112,223,594};
int len = arr.length;
int index = binarySearch(arr, 223);
System.out.println("Element 223 is found at index: " + index);
}
The time complexity of the algorithm is O(log n) since we’re reducing the input by half of the earlier input with each iteration.
The above algorithm works if the array is sorted in ascending order. If the array is sorted in descending order, you can try using > in place of < and vice versa. I’m leaving that to you as a small exercise.
You can also use binary search in association with a custom comparator given that the array is of wrapper objects rather than primitives. Because comparators work with objects, not primitives. Below is a demonstration of using custom comparator to binary search an Integer in an array that’s sorted in ascending order.
int binarySearch(Integer[] arr, Integer target, Comparator comparator) {
int start = 0, end = arr.length - 1;
while(start <= end) {
int mid = start + (end - start) / 2;
int difference = comparator.compare(arr[mid], target);
if(difference == 0) return mid;
else if(difference > 0) end = mid - 1;
else start = mid + 1;
}
return -1;
} void testBinarySearch() {
Integer[] arr = new Integer[]{1,3,5,23,33,112,223,594};
int len = arr.length;
int index = binarySearch(arr, 223, Collections.reverseOrder());
System.out.println("Element 223 is found at index: " + index);
}
The binary search approach can be used for several other problems. Below are some problems where you can use the above approach.
Refer to the problem in this link: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
This is the Question:
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
The property of a Binary Search Tree is that for any given node, all the elements in its left subtree are less than the current node’s value and all the elements in its right subtree are greater than the current node’s value.
Given the property of BST and that we want to convert to it to a height balanced binary tree-which means that the height of the left subtree and the height of the right subtree shouldn’t differ by more than 1 at any given node: The middle element of the array becomes the root of the BST. The given problem can be translated to binary searching the next appropriate value as the root’s left and right children. I have solved the problem below using recursion. Because solving tree problems using recursion seems more intuitive to me. You may try solving the same using iteration as an exercise.
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return sortedArrayToBST(nums, 0, nums.length-1);
}
TreeNode sortedArrayToBST(int[] nums, int start, int end) {
if(start > end) return null;
int mid = start + (end - start)/2;
TreeNode root = new TreeNode(nums[mid]);
root.left = sortedArrayToBST(nums, start, mid-1);
root.right = sortedArrayToBST(nums, mid+1, end);
return root;
}
}The time complexity of the above algorithm is O(n) because we’re visiting each node exactly once. The space complexity is O(log n) because, I have used recursion here.
Here are some more problems that can be solved using binary search algorithm. You can practice them to understand the algorithm better:
Hope the article helped you learn about binary search algorithm. If you have any queries regarding the article or suggest any edits/improvements, feel free to post a comment.
