# LeetCode -35. Search Insert Position

### 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的範圍。

### 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")
``````