35. 搜索插入位置(Swift版)

一、题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 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