Search Insert Position

Given a sorted array of distinct integers and a target, return the index if found, or the index where it would be inserted to keep the array sorted.

Example

Input: nums = 1 3 5 6, target = 2 Output: 1

Approach

Standard binary search — when the loop ends without finding the target, low is exactly the correct insertion point.

Input format

Line 1: the array, space-separated Line 2: target