#9Insert Position in a Spacecraft Cargo List
EasyArrayBinary SearchSearchingDivide and Conquer
You are organizing cargo modules in a spacecraft. The modules are represented by distinct integer IDs arranged in ascending order.
Given a sorted array modules and a new cargo module ID target, return:
the index of target if it already exists, or the index where it should be inserted to keep the modules sorted.
Your algorithm must run in O(log n) time.
Examples
Example 1
Input: modules = [12, 25, 38, 50, 71], target = 38
Output: 2
Explanation: Module 38 already exists at index 2.
Example 2
Input: modules = [12, 25, 38, 50, 71], target = 30
Output: 2
Explanation: 30 should be inserted between 25 and 38.
Example 3
Input: modules = [12, 25, 38, 50, 71], target = 90
Output: 5
Explanation: 90 should be placed at the end.
Constraints
- 1 <= modules.length <= 2 * 10^5
- -10^9 <= modules[i] <= 10^9
- modules contains distinct integers
- modules is sorted in strictly ascending order
- -10^9 <= target <= 10^9