704. Binary Search

Prompt

You’re given an integer array called , sorted in ascending order. You’re also given a and your task is to search for the within and return the index. If the doesn’t exist within , return .

The challenge of this problem is to come up with an algorithm that runs in O(logn) time complexity.

Approach

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 might lie in by locating the middle index of a specified range and using the middle index’s value to compare it with the .

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 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 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 . Because the range in which we are searching for our 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 .

Essentially, this same concept is being applied in Binary Search which is why this technique’s time complexity unsurprisingly is .

Code

Python

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.

Discord

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 cloudiosx@gmail.com

LinkedIn

Portfolio

GitHub

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com