427. Search Insert Position

Given a sorted array nums of distinct integers and a target, return the index if the target is found. If not found, return the index where it would be inserted to keep the array sorted. Solve in O(log n).

Input: A sorted distinct integer array nums and integer target.

Output: Index of target, or insertion position.

Examples

Input: [1,3,5,6], 5
Output: 2
Explanation: 5 is at index 2.

Input: [1,3,5,6], 2
Output: 1
Explanation: 2 is not in array; insert at index 1 (between 1 and 3).

Input: [1,3,5,6], 7
Output: 4
Explanation: 7 > all elements; insert at end (index 4).

Constraints

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4
• All distinct
• Sorted ascending

Asked by