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:
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:
Time Complexity: O(N), best case is O(1).
Space Complexity: O(1).
Solution #2: Binary Search Solution:
Explain Binary Search Process:
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:
Thus we stop when two pointers meet.
Python Code:
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!
