[LeetCode] 35. Search Insert Position

轉自LeetCode

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

<Solution>

這題就用 binary search 來做

那注意一個地方是

當 nums[mid] > target 的時候，right = mid 而不是 right = mid - 1

這樣當 target 不在 nums 裡，且又沒超過 nums 的最大最小值

就返回 right

code 如下
c++

這邊有統整一下 binary search 使用的一些情境，可以拿來參考

kotlin