Binary SearchArray
Given a sorted array of distinct integers and a target, return the index where the target is found. If it is not found, return the index where it would be inserted to keep the array sorted.
Input
Line 1: n and the target. Line 2: n integers in ascending order.
Output
Print the index.
Constraints
1 <= n <= 10^5 -10^9 <= each value, target <= 10^9
Example 1
Input
4 5 1 3 5 6
Output
2
5 is already at index 2.
Example 2
Input
4 2 1 3 5 6
Output
1
2 would be inserted at index 1.