Grokking Binary Search for Coding Interviews_468 x 60 copy.png

Binary Search (BS) is, arguably, the most popular question in coding interviews. Even when you see that a problem can be solved with BS, it can be tricky to handle all of the indexes and base cases in the solution. What if there was an approach that could work for all BS problems? 
This course was designed from scratch with this one goal in mind. We'll explore one technique that can handle any BS problem. The practice problems in this course were carefully chosen to cover the most frequently asked BS questions in coding interviews. At the end of this course, you will feel confident to handle BS questions during phone or on-site interviews, as well as with all of the follow-ups about its time and space complexity.

Binary Search for Coding Interviews

What will be the **space complexity** for binary search in terms of **Big O notation**?

What will be the space complexity for binary search in terms of Big O notation?

What will be the **time complexity** for binary search in terms of **Big O notation**?


What will be the time complexity for binary search in terms of Big O notation?

## Time complexity

The essential property of binary search is to reduce the search area to, nearly, half of the original size.

Suppose we have n` elements in our search array. On each iteration, we’re down to ​ 2n elements. The search area keeps halving from n to ​2​n, to 4​n, to 8n, and so on, until the area becomes of size 1 (unless we found the target in some previous step).

At this point, we either find the value or prove that it doesn’t exist in the search array.

The total runtime is then a matter of how many steps (dividing _n_ by `2` each time) we can take until _n_ becomes `1`.

Here is a visual representation of our algorithm for the worst cases:
- When the target is the first element in the array:

- When the target is the last element in the array:

There are $17$ elements in our array. To find the number of times we have to do halving to ended up with only one item we use a logarithm function $log_2 \space 17=4$. Thus at most $4$ iterations will be enough to reduce our array to one element. If $n$ represents the total number of items, in $log_2 \space n$ operations the answer will be found, which is asymptotically equivalent to $O(log_2 \space n)$.

# Time complexity

The essential property of binary search is to reduce the search area to, nearly, half of the original size.

Suppose we have n` elements in our search array. On each iteration, we’re down to ​ 2n elements. The search area keeps halving from n to ​2​n, to 4​n, to 8n, and so on, until the area becomes of size 1 (unless we found the target in some previous step).

At this point, we either find the value or prove that it doesn’t exist in the search array.

The total runtime is then a matter of how many steps (dividing _n_ by `2` each time) we can take until _n_ becomes `1`.

Let's discuss how fast binary search is and how much memory it uses.

__default

Complexity Analysis

Time complexity