# 704. Binary Search

Leetcode #:704Binary Search

Name:Easy

Difficulty:Amazon, Google, Meta, Microsoft

Companies asked:https://leetcode.com/problems/binary-search/

Link:

# Prompt

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.

# 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 B**inary 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*.

# Code

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