704. Binary Search
Leetcode #: 704
Name: Binary Search
Companies asked: Amazon, Google, Meta, Microsoft
You’re given an integer array called nums, sorted in ascending order. You’re also given a target and your task is to search for the target within nums and return the target’s index. If the target doesn’t exist within nums, return -1.
The challenge of this problem is to come up with an algorithm that runs in O(logn) time complexity.
The approach to this problem is quite straightforward and the technique is exposed in the name of the problem itself. To solve this problem with a solution that satisfies the O(logn) time complexity requirement, we should use the Binary Search technique.
For those of you who don’t know how the Binary Search technique works, it’s a strategy that essentially allows you to narrow down a range where, in this case, your target might lie in by locating the middle index of a specified range and using the middle index’s value to compare it with the target.
The Binary Search technique generally utilizes dual pointers that are initialized from each respective ends of the array. We calculate a middle index and compare its value with the target to see which range (in this case, start of the array to the middle index − 1 OR middle index + 1 to the end of the array) we should analyze, which implies that we don’t bother analyzing the other range that we left out as we can safely deduce that our target shouldn’t lie anywhere within it.
nums = [-1,0,3,5,9,12]
target = 9
left = 0
right = len(nums) - 1
mid = (left + right) // 2 # we want to use floor division to round down and avoid using any floating point numbermid -> (5 + 0) // 2 = 2
Our mid is 2, which is less than our target; therefore, we know that our target lies somewhere within the range of index 3 to 5 inclusive. We wouldn't bother looking any further into any elements that lie within the range of index 0 to 2 inclusive.
The methodology behind Binary Search is that we continually keep reducing the range in which we need to search by 1/2 until we either find or don’t find our target. Because the range in which we are searching for our target is getting reduced by 1/2 potentially multiple times, it’s equivalent to the scenario of a tree — at every level in the tree, the subproblem size of an array becomes smaller and smaller until it reaches the leaf level or the base case where the subproblem size or array size might be 1 or 0 (i.e. Merge Sort or Quick Sort). The point is that in that case the height of the tree for a complete, balanced tree is mathematically proven to be log base 2 of n or simply logn.
Essentially, this same concept is being applied in Binary Search which is why this technique’s time complexity unsurprisingly is logn.
Thank you for reading!
In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.
If you have any questions or comments, please don’t be afraid to connect with me on any of the platforms below or feel free to send me an email at firstname.lastname@example.org