一、题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 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
二、解题
方法一：
直接遍历(searchInsert())
时间复杂度：O(n)。空间复杂度：O(1)。
方法二：
用二分法(searchInsert1())
时间复杂度：O(log(n))。空间复杂度：O(1)。
实际在LeetCode上运行测试用例，方法一和方法二执行时间差不多，想来应该是测试用例数据量比较小的原因。
三、代码实现
class Solution {
func searchInsert(_ nums: [Int], _ target: Int) -> Int {
for (index, n) in nums.enumerated() {
if n >= target {
return index
}
}
return nums.count
}
func searchInsert1(_ nums: [Int], _ target: Int) -> Int {
var low = 0
var high = nums.count
var mid = 0
while low < high {
mid = (high + low) / 2
if nums[mid] > target {
high = mid
}else if nums[mid] < target {
low = mid + 1
}else{
return mid
}
}
return low
}
}
Demo地址：github
