Iterative:

// Time complexity: O(logn)
func searchInsert(_ nums: [Int], _ target: Int) -> Int {
    if nums.count == 0 {
        return 0
    } else {
        var start = 0
        var end = nums.count - 1
        repeat {
            let index = (start + end) / 2
               if nums[index] == target {
                return index
            } else if nums[index] > target {
                end = index - 1
            } else {
                start = index + 1
            }
        } while start <= end
        return start
    }
}
assert(searchInsert([], 9) == 0, "Error 1")
assert(searchInsert([1], 0) == 0, "Error 2")
assert(searchInsert([1], 2) == 1, "Error 3")


assert(searchInsert([1,2], 2) == 1, "Error 4")
assert(searchInsert([1,3], 2) == 1, "Error 5")
assert(searchInsert([0,1], 2) == 2, "Error 6")
assert(searchInsert([1,3], 0) == 0, "Error 7")

Note: 需注意 while結束的條件，如果結束條件是start < end，則Error 6會發生。因為最後回傳的結果值是回傳start，若結束於start < end，代表回傳值永遠不會超出既有array的範圍。

有趣的是Error 3的case其實和Error 6相似，回傳的結果值都是array最後一個index+1，但是因為Error 3的case中start初始值就已經是array的最後一個index值，所以它仍可以超出既有array的範圍。

Recursive:

func searchInsert(_ nums: [Int], _ target: Int) -> Int {
    return searchHelper(nums, target, 0, nums.count - 1)
}

func searchHelper(_ nums: [Int], _ target: Int, _ left: Int, _ right: Int) -> Int {
    if left > right {
        return left
    } else {
        let index = (left + right) / 2
        if target == nums[index] {
            return index
        } else if target > nums[index] {
            return searchHelper(nums, target, index + 1, right)
        } else {
            return searchHelper(nums, target, left, index - 1)
        }
    }
}
assert(searchInsert([], 9) == 0, "Error 1")
assert(searchInsert([1], 0) == 0, "Error 2")
assert(searchInsert([1], 2) == 1, "Error 3")


assert(searchInsert([1,2], 2) == 1, "Error 4")
assert(searchInsert([1,3], 2) == 1, "Error 5")
assert(searchInsert([0,1], 2) == 2, "Error 6")
assert(searchInsert([1,3], 0) == 0, "Error 7")