题目
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.
Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
Example 4:
Input: nums = [1,3,5,6], target = 0
Output: 0
Example 5:
Input: nums = [1], target = 0
Output: 0
Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
-104 <= target <= 104
题解
题目为简单难度。
解法一：暴力求解法
使用for循环遍历nums数组，从下标0开始按个与目标值target进行对比，如果nums[i]>=target，说明目标值在数组所有元素之前，直接返回i即可；另一种情况就是目标值在数组所有元素之后，这时返回nums数组长度len(nums)即可。
//Go
func searchInsert(nums []int, target int) int {
for i := 0;i <len(nums);i++ {
if nums[i] >= target {
return i
}
}
return len(nums)
}
执行结果：
leetcode：
Runtime: 4 ms, faster than 88.29% of Go online submissions for Search Insert Position.
Memory Usage: 3.1 MB, less than 100.00% of Go online submissions for Search Insert Position.
leetcode-cn：
执行用时：4 ms, 在所有 Go 提交中击败了90.15%的用户
内存消耗：2.9 MB, 在所有 Go 提交中击败了100.00%的用户
解法二：二分查找法
//Go
func searchInsert(nums []int, target int) int {
low := 0
high := len(nums) - 1
for low <= high {
// 下方写法为了防止数据溢出，如果先加在除以2 加完的值可能会大于INT_MAX，造成溢出
mid := low + (high - low) / 2
guess := nums[mid]
if guess == target {
return mid //找到了，返回下标
}
if guess > target {
high = mid - 1
} else {
low = mid +1
}
}
return low //没找到
}
执行结果：
leetcode-cn：
执行用时：4 ms, 在所有 Go 提交中击败了90.15%的用户
内存消耗：3 MB, 在所有 Go 提交中击败了56.60%的用户
leetcode：
Runtime: 8 ms, faster than 8.78% of Go online submissions for Search Insert Position.
Memory Usage: 3.3 MB, less than 6.08% of Go online submissions for Search Insert Position.
解法三：golang-sort.SearchInts包
解题时不推荐。
//Go
func searchInsert(nums []int, target int) int {
return sort.SearchInts(nums, target)
}
执行结果：
leetcode：
Runtime: 4 ms, faster than 88.29% of Go online submissions for Search Insert Position.
Memory Usage: 3.1 MB, less than 100.00% of Go online submissions for Search Insert Position.
leetcode-cn：
执行用时：4 ms, 在所有 Go 提交中击败了90.15%的用户
内存消耗：3 MB, 在所有 Go 提交中击败了56.60%的用户
