题目

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.

就是有一组有序的数组和一个目标数字，如果目标数字存在在数组里面，就返回数组下标。如果不存在，则返回把目标数字按大小排列在数组里面的下标。

解法

解法1

1
2
3
4
5
6
7
8
func searchInsert(nums []int, target int) int {
	for n, v := range nums {
		if target <= v {
			return n
		}
	}
	return len(nums)
}

解法2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func searchInsert2(nums []int, target int) int {
	low, high := 0, len(nums)-1
	for low <= high {
		mid := (low + high) / 2
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			high = mid - 1
		} else {
			low = mid + 1
		}
	}
	return low
}

总结

解法2用到了二分法，时间复杂度是logn。在计算时间复杂度的时候，可以把high认为是一个常数，那么只有low在变化。

源代码

https://github.com/liguoqinjim/leetcodeGo/tree/master/problems/lab0035