Binary Search Deep Dive
What is Binary Search?
Wikipedia article expresses it as:
… a search algorithm that finds the position of a target value within a sorted array.
As one of the most fundamental and useful algorithms in computer science, binary search looks for a specific value in an ordered collection.
Why is this important?
Search is a key capability behind many software programs we use in everyday life. For example, when customers shop for deals on travel websites such as priceline.com, efficient implementation of search is critical to our ability to get the best possible travel deals back to the customer as quickly as possible.
One basic type of search is binary search. While binary search provides limited comparative gains when running with small datasets, typically comprised of numerical values, it provides an important benefit when dealing with large datasets that may contain billions of elements, at a fairly performant runtime.
On average, the time complexity is O(log n), where n is the number of elements in the collection. This article shares good insight into the Big-O notation in time complexity of binary search.
The space complexity is O(1) in iterative implementation, since it’s a constant space solution. In recursive implementation, it takes O(log n) space for the recursion call stack.
How does it work?
The algorithm searches the ordered collection (e.g. sorted array), and iterates continuously in half of its size, until the target element is found.
With each iteration, check if the middle element in the sorted array is less than, or equal to the target.
If the middle element is equal to the target, congratulations! Binary search finds the target.
If the middle element is less than the target, search on the left space of the middle element.
If the middle element is greater than the target, search on the right.
Search continuously until either the matching element is found, or the target is not found in the given ordered collection.
Implementation
There are several general patterns to implement Binary Search, about which I’ll be blogging in future parts of the Binary Search Deep Dive series.
In this blog, let’s take a look at a couple of patterns. In each pattern, we will also use a couple of programming languages to look into the nuances between the languages for extra fun 🤠.
Problem
Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.
Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1
Note:
You may assume that all elements in nums are unique.
n will be in the range [1, 10000].
The value of each element in nums will be in the range [-9999, 9999].
Iterative Pattern
Observations between Languages
In JavaScript, the mid index calculation seems rigorous:
const mid = Math.floor(low + (high — low) / 2);The calculation takes the “floor” of a decimal number, (e.g. take 12 from 12.45, where 12 is referred to as the floor). JavaScript seems to require the “Math.floor” code. Otherwise, the results are incorrect due to the decimal rounding of the language.
One may wonder why not go with simplistic math in inner code such as 👇🏻?
const mid = Math.floor((low + high) / 2);Since numbers are stored up to “64 bits”, avoid using math like “low + high”, where the really big number with digits (i.e. exceeding “64 bits”) would crash the program, while math like “low + (high — low) / 2” is safer to avoid Integer Overflow.
In Java, the mid index calculation is:
int mid = (low + high) >>> 1;This wicked looking >>> operator takes advantage of the unsigned right bit-shift operator. It effectively divides the operand by 2 to the power of the right operand, or just 2 here.
Java enthusiasts may wonder if the>> operator could have done the same. The difference between the >> operator and the >>> operator would only show up, when shifting negative numbers. The >> operator shifts a 1 bit into the most significant bit if it was a 1, and the >>> operator shifts in a 0 regardless.
Note that in the following Recursive Pattern in Java, it would use the following snippet, to demonstrate that Java version does not require the “floor” code, yet another topic to deep dive why in a future blog.
int mid = low + (high — low) / 2;Recursive Pattern
Observation
Recursive pattern has the same time complexity as O(log n) and space complexity as O(log n). The boilerplate code seems to be “heavier.” Some research online also seems to suggest that generally people tend to be either iterative or recursive thinkers, and that it may be challenging to grasp both fluently.
I tend to agree with that hypothesis in that, personally, I would grasp iterative approach easier in algorithmic problem resolving over recursive solutions.
Conclusion
Binary search has been proven to be effective in large data sets at lightning speed for many enterprise / business applications, where output is desired, or even demanded, to be fast. Think about the real-time airline prices that could change constantly in milliseconds, and real-time deals that need to be found based on the new prices!
Searching through large data sets is unavoidable for software engineers in their careers. Honing binary search in computational problem solving skills can be helpful in writing reliable, performant code to build useful, resilient products for customers.
The bulk of the world’s data is likely to be unordered. Honing sorting algorithms would also be valuable skills. In the near future, I hope to write another blog to go over other code patterns in binary search in conjunction with a few sorting algorithms, to share how computer science applies to real-world enterprise / business problem solving.
