二分查找—Swift代码模板

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