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