4. [简单] 搜索插入位置

# 出题内容
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:
```
输入: [1,3,5,6], 5
输出: 2
```

示例 2:
```
输入: [1,3,5,6], 2
输出: 1
```
示例 3:
```
输入: [1,3,5,6], 7
输出: 4
```
示例 4:
```
输入: [1,3,5,6], 0
输出: 0
```

# 代码参考

```go
package main

import "fmt"

// 搜索插入位置

// 使用map遍历查询
func searchInsert1(nums []int, val int) int {
	m := make(map[int]int)

for k, v := range nums {
		m[k] = v
	}

for k, v := range m {
		if v == val {
			fmt.Println(v, val, k)
			return k
		} else if v < val && val < m[k+1] {
			m[k+1] = val
			return k + 1
		}
	}
	return 0
}

// 使用二分法插入
func searchInsert2(nums []int, val int) int {
	len := len(nums)
	l, r := 0, len-1
	for l <= r {
		mid := (r + l) / 2
		switch {
		case nums[mid] > val:
			r = mid - 1
		case nums[mid] < val:
			l = mid + 1
		default:
			return mid
		}
	}
	return l
}

func main() {
	fmt.Println("index: ", searchInsert1([]int{1, 3, 4, 6}, 5))
	fmt.Println("index: ", searchInsert2([]int{1, 3, 4, 6}, 9))
}
```

# 代码原理
无

# 输出结果
```
index:  3
index:  4
```