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
}
還有一個(gè)模板更高級(jí)一些，用于解決某些類型的問題：
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
}
復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(logn)瑞躺，其中 n 是數(shù)組的長(zhǎng)度。
- 空間復(fù)雜度：O(1)。
