題目
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
解題思路
本題相當(dāng)于求大于target的最小值的pos，特殊情況是target大于最大值，pos=len(nums)
使用二分法求解
代碼
searchInsertPos.go
package _35_Search_Insert_Position
func SearchInsert(nums []int, target int) int {
len1 := len(nums)
if target > nums[len1-1] {
return len1
}
l := 0
r := len1
for ; l < r ; {
middle := (l + r) / 2
if nums[middle] == target {
return middle
}
if nums[middle] < target {
l = middle + 1
} else {
r = middle
}
}
// l == r
return l
}
測試
searchInsertPos_test.go
package _35_Search_Insert_Position
import "testing"
func TestSearchInsert(t *testing.T) {
var tests = []struct{
input []int
target int
output int
}{
{[]int{1, 3, 5, 6}, 1, 0},
{[]int{1, 3, 5, 6}, 3, 1},
{[]int{1, 3, 5, 6}, 5, 2},
{[]int{1, 3, 5, 6}, 6, 3},
{[]int{1, 3, 5, 6}, 0, 0},
{[]int{1, 3, 5, 6}, 2, 1},
{[]int{1, 3, 5, 6}, 7, 4},
{[]int{1, 3}, 2, 1},
}
for _, v := range tests {
ret := SearchInsert(v.input, v.target)
if ret == v.output {
t.Logf("pass")
} else {
t.Errorf("fail, want %+v, get %+v\n", v.output, ret)
}
}
}
