题目

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

解题思路

本题相当于求大于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)
        }
    }
}