Crack Leetcode 35: Search Insert Position

There is a way to make it easy.

Sometimes they make it look hard, while in fact, there’s always a way you can easily understand. Today, we’ll crack leetcode 35 — Search insertion position — together. After this article, you will learn or refresh your memory about Binary Search. Without further ado, let’s get started.

Problem Description:

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post
(photo taken from Leetcode: https://leetcode.com/problems/search-insert-position/)

Solution:

There is a brute-force solution, as shown below, but today I want to discuss Binary Search with this problem.

Solution #1: Brute-force solution:

Image for post
Image for post

Time Complexity: O(N), best case is O(1).

Space Complexity: O(1).

Solution #2: Binary Search Solution:

Explain Binary Search Process:

Image for post
Image for post
Image for post
Image for post
Image for post
Image for post

We can use a while loop for the above process. Then when to stop?

If we recall the logic, every round we grey out half the elements in the elements not greyed out. Therefore, the left over (not greyed out) length changes from N -> N/2 -> N/4.. all the way to 1. So the base case is like this:

Image for post
Image for post

Thus we stop when two pointers meet.

Python Code:

Image for post
Image for post

Complexity Analysis:

  • Time Complexity:

Every time we grey out half the elements in left-over elements. Assume we have k rounds before while-loop ends. Then we have N/(2^k) = 1. =>k=log2(N).

So the time complexity is O(logN).

*Best case time complexity is O(1).

  • Space Complexity:

Since it used constant auxiliary space, the Space Complexity = O(1)

The END:

Thanks for reading! Please check our articles more often, if you’d like to support our work — and we’ll see you in the next one!

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