Search Insert Position

Given a sorted array of distinct integers nums and an integer target, return the index if the target is found. If not found, return the index where it would be inserted in order.

Function signature

func SearchInsert(nums []int, target int) int

Example

nums = [1,3,5,6], target = 5
output = 2

nums = [1,3,5,6], target = 2
output = 1

Constraints

• 0 <= len(nums) <= 200_000
• -1_000_000_000 <= nums[i], target <= 1_000_000_000
• nums is sorted strictly increasing

Notes

• Use binary search in O(log n).