README
¶
Name
24 - find the insertion index
Description
Problem
Given a sorted array with unique values and a target number, return the index of the given number. If the number is not found, return the index where the number should be placed.
Examples
The input array is [1, 3, 5, 7]. Consider following scenarios:
- the target number is 3 and the return value is 1.
- the target number is 4 and the return value is 2.
Solution
Solution
Use binary search to lookup for the target number. If the number is found, return the index, else return the next index of the last checked number.
Complexity:
- time: O(log(n))
- space: O(1)
Directories
Click to show internal directories.
Click to hide internal directories.