Swift代码模板
func binarySearch(_ nums: [Int], _ target: Int) -> Int {
var l = 0
var r = nums.count - 1
while l <= r {
let mid = (l + r) >> 1
if nums[mid] == target {
return mid
} else if nums[mid] > target {
r = mid - 1
} else {
l = mid + 1
}
}
return -1
}
还有一个模板更高级一些，用于解决某些类型的问题：
func binarySearch(_ nums: [Int], _ target: Int) -> Int {
var l = 0, r = nums.count
while l < r {
let mid = l + (r - l) / 2
if nums(mid) >= target {
r = mid
} else {
l = mid + 1
}
}
return r
}
复杂度分析
- 时间复杂度：O(logn)，其中 n 是数组的长度。
- 空间复杂度：O(1)。
