題目
Given a sorted array of distinct integers 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 must write an algorithm with O(log n) runtime complexity.
- 題意: 找出相近的nums array中的index ，並且時間複雜度須為O(log n)
解法
- 題目要求: 時間複雜度為 O(log n) ，所以可以使用Binary Search 方法來找出index
func searchInsert(nums []int, target int) int {
start := 0
end := len(nums) - 1
for start <= end {
mid := start + (end-start)/2
if nums[mid] == target {
return mid
} else if nums[mid] > target {
end = mid - 1
} else {
start = mid + 1
}
}
return start
}
- 加些測試，看看結果是不是如預期
import (
"github.com/stretchr/testify/assert"
"testing"
)
func Test_searchInsert_case1(t *testing.T) {
nums := []int{1, 3, 5, 6}
assert.Equal(t, 2, searchInsert(nums, 5))
}
func Test_searchInsert_case2(t *testing.T) {
nums := []int{1, 3, 5, 6}
assert.Equal(t, 1, searchInsert(nums, 2))
}
func Test_searchInsert_case3(t *testing.T) {
nums := []int{1, 3, 5, 6}
assert.Equal(t, 4, searchInsert(nums, 7))
}