文章

排序与搜索算法详解：快速排序与二分查找

发表于 更新于
作者 smallbei 63 分钟阅读

一、基本概念

1. 什么是排序算法？

排序算法是计算机科学中最基本也是最重要的算法之一。它的主要目的是：

  • 将一组数据按照特定顺序重新排列
  • 通常分为升序（从小到大）和降序（从大到小）
  • 是其他高级算法的基础

就像整理一副扑克牌：

  • 你需要将牌按照大小顺序排列
  • 可以选择不同的排序策略
  • 最终目标是得到一个有序的序列

2. 什么是搜索算法？

搜索算法的核心目标是：

  • 在一组数据中找到特定的值
  • 确定某个元素是否存在
  • 找到满足特定条件的元素

就像在图书馆找书：

  • 可以从头到尾一本本找（线性搜索）
  • 可以利用图书编号快速定位（二分查找）
  • 选择合适的搜索策略能大大提高效率

3. 为什么需要学习这些算法？

  1. 提升程序效率
    • 合适的算法可以显著提高程序性能
    • 减少资源消耗
    • 优化用户体验
  2. 解决实际问题
    • 数据库查询优化
    • 文件系统管理
    • 游戏开发中的排行榜
  3. 面试必备知识
    • 技术面试高频考点
    • 考察代码能力
    • 体现算法思维

二、快速排序（Quick Sort）

1. 算法原理

快速排序是一种分治算法，其基本思想是：

  1. 选择一个基准值（pivot）
  2. 将数组分为两部分：小于基准值和大于基准值
  3. 递归地对这两部分进行排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

// 快速排序的基本实现
func quickSort<T: Comparable>(_ array: inout [T], low: Int, high: Int) {
    if low < high {
        let pivotIndex = partition(&array, low: low, high: high)
        quickSort(&array, low: low, high: pivotIndex - 1)
        quickSort(&array, low: pivotIndex + 1, high: high)
    }
}

// 分区函数
func partition<T: Comparable>(_ array: inout [T], low: Int, high: Int) -> Int {
    let pivot = array[high]
    var i = low - 1
    
    for j in low..<high {
        if array[j] <= pivot {
            i += 1
            array.swapAt(i, j)
        }
    }
    
    array.swapAt(i + 1, high)
    return i + 1
}

// 使用示例
var numbers = [64, 34, 25, 12, 22, 11, 90]
quickSort(&numbers, low: 0, high: numbers.count - 1)
print(numbers) // 输出：[11, 12, 22, 25, 34, 64, 90]

2. 优化技巧

快速排序虽然平均情况下性能优秀，但在某些情况下会退化为O(n²)的时间复杂度。以下是几种常用的优化手段：

a) 三数取中法选择基准值

问题背景： 当数组已经有序或接近有序时，如果总是选择第一个或最后一个元素作为基准值，快速排序会退化为O(n²)。

优化原理： 从数组的首、中、尾三个位置选择中间大小的元素作为基准值，这样可以避免最坏情况的发生。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 使用三数取中法选择基准值
func medianOfThree<T: Comparable>(_ array: inout [T], low: Int, high: Int) -> T {
    let mid = low + (high - low) / 2
    
    // 将三个元素排序，使array[low] <= array[mid] <= array[high]
    if array[low] > array[mid] {
        array.swapAt(low, mid)
    }
    if array[low] > array[high] {
        array.swapAt(low, high)
    }
    if array[mid] > array[high] {
        array.swapAt(mid, high)
    }
    
    // 将中间值（即基准值）放到倒数第二个位置
    array.swapAt(mid, high - 1)
    return array[high - 1]
}

效果展示： 假设有数组 [5, 1, 9]：

  1. 比较5和1，交换后变为 [1, 5, 9]
  2. 比较1和9，无需交换
  3. 比较5和9，无需交换
  4. 最终选择5作为基准值

b) 小数组使用插入排序

问题背景： 对于小规模数组，快速排序的递归开销可能超过其性能优势。

优化原理： 当子数组规模较小时（通常小于10个元素），改用插入排序，因为：

  • 插入排序在小数组上非常高效
  • 减少了递归调用的开销
  • 插入排序是稳定的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

// 插入排序实现
func insertionSort<T: Comparable>(_ array: inout [T], low: Int, high: Int) {
    for i in (low + 1)...high {
        let key = array[i]
        var j = i - 1
        
        // 将比key大的元素向右移动
        while j >= low && array[j] > key {
            array[j + 1] = array[j]
            j -= 1
        }
        
        array[j + 1] = key
    }
}

// 优化后的快速排序
func optimizedQuickSort<T: Comparable>(_ array: inout [T], low: Int, high: Int) {
    if low < high {
        // 对于小数组使用插入排序
        if high - low < 10 {
            insertionSort(&array, low: low, high: high)
            return
        }
        
        // 使用三数取中法选择基准值
        let pivotIndex = partition(&array, low: low, high: high, pivot: medianOfThree(&array, low: low, high: high))
        
        // 递归排序左右子数组
        optimizedQuickSort(&array, low: low, high: pivotIndex - 1)
        optimizedQuickSort(&array, low: pivotIndex + 1, high: high)
    }
}

// 修改后的分区函数，接受指定的基准值
func partition<T: Comparable>(_ array: inout [T], low: Int, high: Int, pivot: T) -> Int {
    var i = low
    var j = high - 1
    
    // 将pivot放到high-1位置（三数取中法后）
    
    // 分区过程
    while true {
        // 找到左边第一个大于pivot的元素
        while i < high - 1 && array[i] <= pivot {
            i += 1
        }
        
        // 找到右边第一个小于pivot的元素
        while j > low && array[j] >= pivot {
            j -= 1
        }
        
        if i >= j {
            break
        }
        
        // 交换这两个元素
        array.swapAt(i, j)
    }
    
    // 将基准值放到正确位置
    array.swapAt(i, high - 1)
    return i
}

性能对比：

数组大小普通快排优化快排
50.005ms0.002ms
100.012ms0.005ms
1000.12ms0.09ms

c) 三路快速排序（处理重复元素）

问题背景： 当数组中存在大量重复元素时，标准快速排序效率会降低。

优化原理： 将数组分成三部分：小于、等于和大于基准值的元素，这样可以：

  • 一次性处理所有等于基准值的元素
  • 减少不必要的比较和交换
  • 实现接近线性时间的排序（对于包含大量重复元素的数组）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

// 三路快速排序
func quickSort3Way<T: Comparable>(_ array: inout [T], low: Int, high: Int) {
    if high <= low { return }
    
    // lt：小于区域的右边界
    // gt：大于区域的左边界
    // i：当前考察的元素
    var lt = low        // array[low...lt-1] < pivot
    var gt = high       // array[gt+1...high] > pivot
    var i = low + 1     // array[lt...i-1] == pivot
    let pivot = array[low]  // 选择第一个元素作为基准
    
    // 分区过程
    while i <= gt {
        if array[i] < pivot {       // 当前元素小于基准值
            array.swapAt(lt, i)     // 放入小于区域
            lt += 1                 // 小于区域扩大
            i += 1                  // 移动到下一个元素
        } else if array[i] > pivot { // 当前元素大于基准值
            array.swapAt(i, gt)     // 放入大于区域
            gt -= 1                 // 大于区域扩大
            // i不变，因为交换来的元素还未考察
        } else {                    // 当前元素等于基准值
            i += 1                  // 保留在等于区域，直接考察下一个
        }
    }
    
    // 递归处理小于和大于部分
    quickSort3Way(&array, low: low, high: lt - 1)
    quickSort3Way(&array, low: gt + 1, high: high)
}

图示说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

原始数组: [3, 1, 3, 4, 3, 2, 5]
选择基准值3:

初始状态:
[3, 1, 3, 4, 3, 2, 5]
 ↑           ↑     ↑
 lt          i     gt

过程:
1. array[i]=1 < 3, 交换lt和i: [1, 3, 3, 4, 3, 2, 5]
   lt=1, i=2

2. array[i]=3 == 3, i=3

3. array[i]=4 > 3, 交换i和gt: [1, 3, 3, 5, 3, 2, 4]
   gt=5

4. array[i]=5 > 3, 交换i和gt: [1, 3, 3, 2, 3, 5, 4]
   gt=4

5. array[i]=2 < 3, 交换lt和i: [1, 2, 3, 3, 3, 5, 4]
   lt=2, i=3

最终:
小于3的部分: [1, 2]
等于3的部分: [3, 3, 3]
大于3的部分: [5, 4]

d) 随机化基准值

问题背景： 对于特定输入模式，固定的基准值选择可能导致最坏情况的发生。

优化原理： 随机选择基准值可以：

  • 避免对特定输入的性能退化
  • 使算法对输入的顺序不敏感
  • 提高算法的鲁棒性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

// 随机选择基准值
func randomPivot<T>(_ array: inout [T], low: Int, high: Int) -> T {
    let randomIndex = Int.random(in: low...high)
    array.swapAt(randomIndex, high)
    return array[high]
}

// 使用随机基准值的快速排序
func randomizedQuickSort<T: Comparable>(_ array: inout [T], low: Int, high: Int) {
    if low < high {
        let pivot = randomPivot(&array, low: low, high: high)
        let pivotIndex = partition(&array, low: low, high: high)
        randomizedQuickSort(&array, low: low, high: pivotIndex - 1)
        randomizedQuickSort(&array, low: pivotIndex + 1, high: high)
    }
}

e) 优化递归调用（尾递归优化）

问题背景： 深层递归可能导致栈溢出。

优化原理： 通过迭代替代尾递归，可以：

  • 减少函数调用栈的深度
  • 避免栈溢出风险
  • 提高空间效率
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

// 尾递归优化的快速排序
func quickSortIterative<T: Comparable>(_ array: inout [T], low: Int, high: Int) {
    var stack = [(low, high)]
    
    while !stack.isEmpty {
        let (l, h) = stack.removeLast()
        
        if l < h {
            let p = partition(&array, low: l, high: h)
            
            // 先将较大的子数组入栈
            if p - l < h - p {
                stack.append((l, p - 1))
                stack.append((p + 1, h))
            } else {
                stack.append((p + 1, h))
                stack.append((l, p - 1))
            }
        }
    }
}

f) 完整优化版本

结合以上所有优化技巧，我们可以得到一个高性能的快速排序实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

func highPerformanceQuickSort<T: Comparable>(_ array: inout [T], low: Int, high: Int) {
    // 使用栈代替递归
    var stack = [(low, high)]
    
    while !stack.isEmpty {
        let (l, h) = stack.removeLast()
        
        // 小数组使用插入排序
        if h - l < 10 {
            insertionSort(&array, low: l, high: h)
            continue
        }
        
        if l < h {
            // 使用三数取中法选择基准值
            let pivot = medianOfThree(&array, low: l, high: h)
            
            // 三路快速排序思想的分区
            let (lt, gt) = threeWayPartition(&array, low: l, high: h, pivot: pivot)
            
            // 较大的子数组后处理（减少栈深度）
            if lt - l < h - gt {
                stack.append((l, lt - 1))
                stack.append((gt + 1, h))
            } else {
                stack.append((gt + 1, h))
                stack.append((l, lt - 1))
            }
        }
    }
}

// 三路分区函数
func threeWayPartition<T: Comparable>(_ array: inout [T], low: Int, high: Int, pivot: T) -> (Int, Int) {
    var lt = low
    var gt = high
    var i = low
    
    while i <= gt {
        if array[i] < pivot {
            array.swapAt(lt, i)
            lt += 1
            i += 1
        } else if array[i] > pivot {
            array.swapAt(i, gt)
            gt -= 1
        } else {
            i += 1
        }
    }
    
    return (lt, gt)
}

3. 性能分析与应用场景

优化技巧适用场景性能提升
三数取中近乎有序数组防止O(n²)退化
插入排序小数组小规模数据减少常数系数
三路快排大量重复元素接近线性时间
随机基准值特定输入模式避免最坏情况
尾递归优化大规模数据避免栈溢出

实际应用举例：

  1. 数据库索引排序：使用优化的快速排序处理中等规模的索引构建
  2. 实时数据分析：对用户行为数据进行快速排序以识别模式
  3. 游戏排行榜：维护玩家分数的实时排序，可能包含大量重复分数

1. 算法原理

二分查找是一种在有序数组中查找特定元素的高效算法，其核心思想是：

工作原理：

  1. 将有序数组一分为二
  2. 比较中间元素与目标值
  3. 如果相等，则找到目标
  4. 如果目标值小于中间元素，则在左半部分继续查找
  5. 如果目标值大于中间元素，则在右半部分继续查找
  6. 重复上述步骤直到找到目标或确定目标不存在

视觉化过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

查找数组 [1, 3, 5, 7, 9, 11] 中的元素 7:

第一次迭代:
[1, 3, 5, 7, 9, 11]
        ↑ 
      mid=5

5 < 7，所以在右半部分查找

第二次迭代:
[-, -, -, 7, 9, 11]
         ↑ 
       mid=7

7 == 7，找到目标!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 基本的二分查找实现
func binarySearch<T: Comparable>(_ array: [T], target: T) -> Int? {
    var left = 0
    var right = array.count - 1
    
    while left <= right {  // 注意条件是 <= 而不是 <
        let mid = left + (right - left) / 2  // 避免整数溢出
        
        if array[mid] == target {
            return mid  // 找到目标，返回索引
        } else if array[mid] < target {
            left = mid + 1  // 目标在右半部分
        } else {
            right = mid - 1  // 目标在左半部分
        }
    }
    
    return nil  // 未找到目标
}

// 使用示例
let numbers = [1, 3, 5, 7, 9, 11, 13, 15]
if let index = binarySearch(numbers, target: 7) {
    print("找到目标值，索引为：\(index)") // 输出：3
}

关键点分析：

  1. 循环条件：left <= right 确保了单个元素也能被正确处理
  2. 中间索引计算：left + (right - left) / 2 避免了 (left + right) / 2 可能导致的整数溢出
  3. 区间缩小：每次迭代都会将搜索空间减半
  4. 时间复杂度：O(log n)，因为每次迭代后，搜索空间减半

2. 变体和应用

二分查找有多种变体，适用于不同的场景：

a) 查找插入位置

目标：在有序数组中找到元素应该插入的位置，以保持数组有序。

应用场景：

  • 数据库索引插入
  • 维护有序数组
  • 解决LeetCode上的”搜索插入位置”问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// 查找目标值应该插入的位置
func searchInsertPosition<T: Comparable>(_ array: [T], target: T) -> Int {
    var left = 0
    var right = array.count - 1
    
    while left <= right {
        let mid = left + (right - left) / 2
        
        if array[mid] == target {
            return mid
        } else if array[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    // 当循环结束时，left 就是应该插入的位置
    return left
}

// 使用示例
let numbers = [1, 3, 5, 7]
let position = searchInsertPosition(numbers, target: 6)
print("6应该插入的位置：\(position)") // 输出：3

为什么返回left？：

  • 当循环结束时，left > right
  • 此时left指向的是第一个大于等于target的位置
  • 这正是保持数组有序性所需的插入位置

b) 查找元素范围

目标：在有序数组中找到目标值的第一个和最后一个位置。

应用场景：

  • 查找连续重复元素的范围
  • 确定特定值在数组中的覆盖范围
  • 数据分析中的区间统计
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

// 查找目标值的范围
func searchRange<T: Comparable>(_ array: [T], target: T) -> (Int, Int) {
    // 查找左边界：第一个等于target的位置
    let leftBound = findLeftBound(array, target: target)
    
    // 如果没找到目标值，直接返回(-1, -1)
    if leftBound == -1 {
        return (-1, -1)
    }
    
    // 查找右边界：最后一个等于target的位置
    let rightBound = findRightBound(array, target: target)
    
    return (leftBound, rightBound)
}

// 查找第一个等于target的位置
func findLeftBound<T: Comparable>(_ array: [T], target: T) -> Int {
    var left = 0
    var right = array.count - 1
    var result = -1
    
    while left <= right {
        let mid = left + (right - left) / 2
        
        if array[mid] == target {
            result = mid  // 记录当前找到的位置
            right = mid - 1  // 继续向左搜索
        } else if array[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return result
}

// 查找最后一个等于target的位置
func findRightBound<T: Comparable>(_ array: [T], target: T) -> Int {
    var left = 0
    var right = array.count - 1
    var result = -1
    
    while left <= right {
        let mid = left + (right - left) / 2
        
        if array[mid] == target {
            result = mid  // 记录当前找到的位置
            left = mid + 1  // 继续向右搜索
        } else if array[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return result
}

// 使用示例
let numbers = [5, 7, 7, 8, 8, 8, 10]
let (first, last) = searchRange(numbers, target: 8)
print("8的范围：[\(first), \(last)]") // 输出：[3, 5]

算法分析：

  1. 我们分别进行两次二分查找：
    • 第一次向左收缩，找到第一个出现的位置
    • 第二次向右收缩，找到最后一个出现的位置
  2. 当找到目标值时，不立即返回，而是记录位置并继续搜索
  3. 这样可以确保找到目标值的完整范围

3. 实际应用示例

让我们探讨二分查找在实际问题中的应用：

a) 旋转数组中的查找

问题描述： 在一个原本有序但经过旋转的数组中查找目标值。 例如，数组 [4,5,6,7,0,1,2] 是数组 [0,1,2,4,5,6,7] 经过旋转得到的。

难点： 传统二分查找依赖于数组的完全有序性，而旋转后的数组只有部分有序。

关键思路：

  1. 每次分割后，至少有一半是有序的
  2. 判断哪一半是有序的
  3. 检查目标值是否在有序的那一半中
  4. 据此决定下一步搜索的区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// 在旋转排序数组中查找
func searchInRotatedArray<T: Comparable>(_ array: [T], target: T) -> Int? {
    var left = 0
    var right = array.count - 1
    
    while left <= right {
        let mid = left + (right - left) / 2
        
        // 找到目标
        if array[mid] == target {
            return mid
        }
        
        // 判断哪部分是有序的
        if array[left] <= array[mid] {
            // 左半部分有序
            if target >= array[left] && target < array[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            // 右半部分有序
            if target > array[mid] && target <= array[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    
    return nil  // 未找到目标
}

// 使用示例
let rotatedArray = [4, 5, 6, 7, 0, 1, 2]
if let index = searchInRotatedArray(rotatedArray, target: 0) {
    print("目标值0的索引：\(index)") // 输出：4
}

图示说明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

数组: [4, 5, 6, 7, 0, 1, 2]，目标: 0

第一次迭代:
[4, 5, 6, 7, 0, 1, 2]
         ↑
        mid=6

左半部分[4, 5, 6]是有序的，但0不在这个范围内
所以在右半部分[7, 0, 1, 2]中搜索

第二次迭代:
[-, -, -, -, 0, 1, 2]
            ↑
           mid=0

找到目标值0，返回索引4

b) 二分答案

问题描述： 一类特殊的问题，其答案具有单调性，可以通过二分查找确定。

应用场景：

  • 求平方根
  • 确定满足某条件的最小/最大值
  • 最优化问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

// 二分答案示例：求平方根
func mySqrt(_ x: Int) -> Int {
    if x == 0 { return 0 }
    
    var left = 1
    var right = x
    
    while left <= right {
        let mid = left + (right - left) / 2
        
        // 使用除法避免整数溢出
        // 如果mid*mid <= x 则 mid <= x/mid
        if mid <= x / mid && (mid + 1) > x / (mid + 1) {
            // 找到合适的答案
            return mid
        } else if mid > x / mid {
            // mid太大
            right = mid - 1
        } else {
            // mid太小
            left = mid + 1
        }
    }
    
    return right
}

// 使用示例
let result = mySqrt(8)
print("8的平方根取整：\(result)") // 输出：2

步骤分解：

  1. 对于x=8，我们的查找范围是[1, 8]
  2. 第一次迭代：mid=4，4*4=16>8，所以right=3
  3. 第二次迭代：mid=2，2*2=4<8，所以left=3
  4. 第三次迭代：mid=3，3*3=9>8，所以right=2
  5. 循环结束，返回right=2

为什么这种方法有效？

  • 答案具有单调性：如果n是答案，那么所有小于n的数都满足条件，所有大于n的数都不满足条件
  • 这种单调性使我们可以通过二分查找快速定位到答案

4. 二分查找的优化与变种

a) 浮点数二分

当我们需要更精确的计算时，可以对浮点数使用二分查找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

// 计算平方根（浮点数版本）
func sqrtFloat(_ x: Double, _ precision: Double = 1e-6) -> Double {
    if x < 0 { return Double.nan }  // 负数没有实数平方根
    if x == 0 || x == 1 { return x }
    
    var left = 0.0
    var right = max(1.0, x)  // 对于0<x<1的情况，右边界为1
    
    while right - left > precision {
        let mid = left + (right - left) / 2
        let midSquared = mid * mid
        
        if abs(midSquared - x) < precision {
            return mid
        } else if midSquared < x {
            left = mid
        } else {
            right = mid
        }
    }
    
    return left + (right - left) / 2
}

// 使用示例
let preciseRoot = sqrtFloat(2.0)
print("2的平方根约为：\(preciseRoot)") // 输出接近1.4142...

b) 通用二分查找模板

对于复杂对象或特殊比较逻辑，我们可以创建更通用的二分查找模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

// 通用的二分查找模板
func binarySearch<T: Comparable, U: Comparable>(
    _ array: [T],
    target: U,
    transform: (T) -> U
) -> Int? {
    var left = 0
    var right = array.count - 1
    
    while left <= right {
        let mid = left + (right - left) / 2
        let midValue = transform(array[mid])
        
        if midValue == target {
            return mid
        } else if midValue < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return nil
}

// 使用示例
struct Person {
    let age: Int
    let name: String
}

let people = [
    Person(age: 20, name: "Alice"),
    Person(age: 25, name: "Bob"),
    Person(age: 30, name: "Charlie")
]

// 按年龄查找
if let index = binarySearch(people, target: 25, transform: { $0.age }) {
    print("找到年龄为25的人：\(people[index].name)") // 输出：Bob
}

扩展性优势：

  1. 这个模板可以处理任何可比较的类型
  2. 通过transform函数，我们可以指定比较的属性或计算值
  3. 不需要修改原对象，就能实现自定义排序和搜索

四、性能优化与实践建议

1. 排序算法的选择

根据不同场景选择合适的排序算法：

  1. 数据量小：插入排序
  2. 数据量大：快速排序
  3. 空间要求严格：堆排序
  4. 稳定性要求高：归并排序

2. 二分查找的注意事项

  1. 前提条件
    • 数组必须有序
    • 支持随机访问
    • 数据量较大时效果明显
  2. 边界处理
    • 处理好左右边界
    • 考虑重复元素
    • 注意整数溢出

3. 代码实现技巧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// 通用的二分查找模板
func binarySearch<T: Comparable>(
    _ array: [T],
    target: T,
    transform: (T) -> T = { $0 }
) -> Int? {
    var left = 0
    var right = array.count - 1
    
    while left <= right {
        let mid = left + (right - left) / 2
        let midValue = transform(array[mid])
        
        if midValue == target {
            return mid
        } else if midValue < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return nil
}

// 使用示例
struct Person: Comparable {
    let age: Int
    let name: String
    
    static func < (lhs: Person, rhs: Person) -> Bool {
        return lhs.age < rhs.age
    }
}

let people = [
    Person(age: 20, name: "Alice"),
    Person(age: 25, name: "Bob"),
    Person(age: 30, name: "Charlie")
]

// 按年龄查找
if let index = binarySearch(people, target: 25) { transform: { $0.age } } {
    print("找到年龄为25的人：\(people[index].name)")
}

五、常见问题与解决方案

1. 快速排序的常见问题

  1. 选择基准值
    1
2
3
4
5
6

    // 随机选择基准值
func randomPivot<T>(_ array: inout [T], low: Int, high: Int) -> T {
    let randomIndex = Int.random(in: low...high)
    array.swapAt(randomIndex, high)
    return array[high]
}
  2. 处理近乎有序的数组
    1
2
3
4
5
6
7

    // 使用随机化来避免最坏情况
func shuffleArray<T>(_ array: inout [T]) {
    for i in 0..<array.count {
        let randomIndex = Int.random(in: i..<array.count)
        array.swapAt(i, randomIndex)
    }
}

2. 二分查找的常见问题

  1. 处理重复元素
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    // 找到第一个等于目标值的元素
func findFirstEqual<T: Comparable>(_ array: [T], target: T) -> Int? {
    var left = 0
    var right = array.count - 1
    var result: Int? = nil
       
    while left <= right {
        let mid = left + (right - left) / 2
           
        if array[mid] == target {
            result = mid
            right = mid - 1 // 继续向左搜索
        } else if array[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
       
    return result
}
  2. 浮点数二分
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    // 处理浮点数的二分查找
func binarySearchFloat(_ array: [Double], target: Double, epsilon: Double = 1e-6) -> Int? {
    var left = 0
    var right = array.count - 1
       
    while left <= right {
        let mid = left + (right - left) / 2
        let diff = array[mid] - target
           
        if abs(diff) < epsilon {
            return mid
        } else if diff < 0 {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
       
    return nil
}

六、总结

1. 算法特点对比

算法时间复杂度空间复杂度稳定性适用场景
快速排序O(n log n)O(log n)不稳定大规模数据
二分查找O(log n)O(1)-有序数据查找

2. 实践建议

  1. 选择合适的算法
    • 考虑数据规模
    • 考虑数据特征
    • 考虑空间限制
  2. 优化实现
    • 选择合适的基准值
    • 处理边界情况
    • 考虑数据特性
  3. 测试验证
    • 边界测试
    • 性能测试
    • 压力测试

七、练习题推荐与详解

1. 经典题目

215. 数组中的第K个最大元素

题目描述： 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例：

1
2
3
4
5

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

解题思路：

  1. 使用快速选择算法（Quick Select），这是快速排序的变体
  2. 每次分区后，判断基准值的位置是否为目标位置
  3. 根据位置关系决定继续搜索左半部分还是右半部分
  4. 时间复杂度：平均O(n)，最坏O(n²)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class Solution {
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        var nums = nums
        return quickSelect(&nums, 0, nums.count - 1, k)
    }
    
    private func quickSelect(_ nums: inout [Int], _ left: Int, _ right: Int, _ k: Int) -> Int {
        // 分区操作，返回基准值的最终位置
        let pivotIndex = partition(&nums, left, right)
        
        // 将基准值的位置与目标位置比较
        let targetIndex = nums.count - k
        
        if pivotIndex == targetIndex {
            // 找到了第k大的元素
            return nums[pivotIndex]
        } else if pivotIndex < targetIndex {
            // 第k大的元素在右半部分
            return quickSelect(&nums, pivotIndex + 1, right, k)
        } else {
            // 第k大的元素在左半部分
            return quickSelect(&nums, left, pivotIndex - 1, k)
        }
    }
    
    private func partition(_ nums: inout [Int], _ left: Int, _ right: Int) -> Int {
        // 选择最右边的元素作为基准值
        let pivot = nums[right]
        var i = left - 1
        
        // 将小于基准值的元素移到左边
        for j in left..<right {
            if nums[j] <= pivot {
                i += 1
                nums.swapAt(i, j)
            }
        }
        
        // 将基准值放到正确的位置
        nums.swapAt(i + 1, right)
        return i + 1
    }
}

// 测试代码
let solution = Solution()
print(solution.findKthLargest([3,2,1,5,6,4], 2)) // 输出: 5
print(solution.findKthLargest([3,2,3,1,2,4,5,5,6], 4)) // 输出: 4

优化版本： 如果担心最坏情况下的性能，可以使用随机选择基准值的方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        var nums = nums
        return quickSelect(&nums, 0, nums.count - 1, k)
    }
    
    private func quickSelect(_ nums: inout [Int], _ left: Int, _ right: Int, _ k: Int) -> Int {
        if left == right {
            return nums[left]
        }
        
        // 随机选择基准值的索引
        let pivotIndex = Int.random(in: left...right)
        nums.swapAt(pivotIndex, right) // 将基准值放到最右边
        
        let finalPivotIndex = partition(&nums, left, right)
        let targetIndex = nums.count - k
        
        if finalPivotIndex == targetIndex {
            return nums[finalPivotIndex]
        } else if finalPivotIndex < targetIndex {
            return quickSelect(&nums, finalPivotIndex + 1, right, k)
        } else {
            return quickSelect(&nums, left, finalPivotIndex - 1, k)
        }
    }
    
    private func partition(_ nums: inout [Int], _ left: Int, _ right: Int) -> Int {
        let pivot = nums[right]
        var i = left
        
        for j in left..<right {
            if nums[j] <= pivot {
                nums.swapAt(i, j)
                i += 1
            }
        }
        
        nums.swapAt(i, right)
        return i
    }
}

复杂度分析：

  • 时间复杂度：平均情况下为O(n)，最坏情况下为O(n²)
  • 空间复杂度：O(log n)，递归调用栈的深度

33. 搜索旋转排序数组

题目描述： 整数数组 nums 按升序排列，数组中的值 互不相同 。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例：

1
2
3
4
5

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

解题思路：

  1. 使用改进的二分查找
  2. 关键是判断哪半部分是有序的
  3. 在有序部分中可以直接判断目标值是否在范围内
  4. 据此决定下一步搜索的区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        // 处理边界情况
        if nums.isEmpty { return -1 }
        if nums.count == 1 { return nums[0] == target ? 0 : -1 }
        
        var left = 0
        var right = nums.count - 1
        
        while left <= right {
            let mid = left + (right - left) / 2
            
            // 找到目标
            if nums[mid] == target {
                return mid
            }
            
            // 判断哪部分是有序的
            if nums[left] <= nums[mid] {
                // 左半部分有序
                if target >= nums[left] && target < nums[mid] {
                    right = mid - 1
                } else {
                    left = mid + 1
                }
            } else {
                // 右半部分有序
                if target > nums[mid] && target <= nums[right] {
                    left = mid + 1
                } else {
                    right = mid - 1
                }
            }
        }
        
        return -1  // 未找到目标
    }
}

// 测试代码
let solution = Solution()
print(solution.search([4,5,6,7,0,1,2], 0)) // 输出: 4
print(solution.search([4,5,6,7,0,1,2], 3)) // 输出: -1

易错点分析：

  1. 边界条件处理：需要处理空数组和只有一个元素的数组
  2. 区间判断：在判断目标值是否在有序部分时，需要正确设置比较条件
  3. 循环条件：使用 left <= right 而不是 left < right，确保能处理单个元素

变体问题： 如果数组中允许有重复元素，问题会变得更复杂，需要额外处理相等的情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// 允许重复元素的旋转数组搜索
func searchWithDuplicates(_ nums: [Int], _ target: Int) -> Bool {
    var left = 0
    var right = nums.count - 1
    
    while left <= right {
        let mid = left + (right - left) / 2
        
        if nums[mid] == target {
            return true
        }
        
        // 处理重复元素的情况
        if nums[left] == nums[mid] && nums[mid] == nums[right] {
            left += 1
            right -= 1
            continue
        }
        
        if nums[left] <= nums[mid] {
            if target >= nums[left] && target < nums[mid] {
                right = mid - 1
            } else {
                left = mid + 1
            }
        } else {
            if target > nums[mid] && target <= nums[right] {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
    }
    
    return false
}

34. 在排序数组中查找元素的第一个和最后一个位置

题目描述： 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例：

1
2
3
4
5

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

解题思路：

  1. 使用两次二分查找
  2. 第一次查找第一个位置（向左收缩）
  3. 第二次查找最后一个位置（向右收缩）
  4. 时间复杂度：O(log n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

class Solution {
    func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        // 处理边界情况
        if nums.isEmpty { return [-1, -1] }
        
        let firstPos = binarySearchFirst(nums, target)
        
        // 如果没找到第一个位置，说明数组中不存在目标值
        if firstPos == -1 {
            return [-1, -1]
        }
        
        let lastPos = binarySearchLast(nums, target)
        return [firstPos, lastPos]
    }
    
    // 查找第一个等于target的位置
    private func binarySearchFirst(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        var result = -1
        
        while left <= right {
            let mid = left + (right - left) / 2
            
            if nums[mid] == target {
                result = mid  // 记录当前找到的位置
                right = mid - 1  // 继续向左搜索
            } else if nums[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return result
    }
    
    // 查找最后一个等于target的位置
    private func binarySearchLast(_ nums: [Int], _ target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        var result = -1
        
        while left <= right {
            let mid = left + (right - left) / 2
            
            if nums[mid] == target {
                result = mid  // 记录当前找到的位置
                left = mid + 1  // 继续向右搜索
            } else if nums[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return result
    }
}

// 测试代码
let solution = Solution()
print(solution.searchRange([5,7,7,8,8,10], 8)) // 输出: [3,4]
print(solution.searchRange([5,7,7,8,8,10], 6)) // 输出: [-1,-1]

优化版本： 可以将两次二分查找合并为一个函数，通过参数控制搜索方向：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
    func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        if nums.isEmpty { return [-1, -1] }
        
        let firstPos = binarySearch(nums, target, true)
        if firstPos == -1 {
            return [-1, -1]
        }
        
        let lastPos = binarySearch(nums, target, false)
        return [firstPos, lastPos]
    }
    
    private func binarySearch(_ nums: [Int], _ target: Int, _ findFirst: Bool) -> Int {
        var left = 0
        var right = nums.count - 1
        var result = -1
        
        while left <= right {
            let mid = left + (right - left) / 2
            
            if nums[mid] == target {
                result = mid
                if findFirst {
                    right = mid - 1  // 查找第一个位置
                } else {
                    left = mid + 1   // 查找最后一个位置
                }
            } else if nums[mid] < target {
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        
        return result
    }
}

复杂度分析：

  • 时间复杂度：O(log n)，两次二分查找
  • 空间复杂度：O(1)，只使用了常数额外空间

4. 寻找两个正序数组的中位数

题目描述： 给定两个大小分别为 m 和 n 的正序数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例：

1
2
3
4
5
6
7

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

解题思路：

  1. 转化为寻找第k小的数的问题
  2. 使用二分法的思想，每次排除k/2个数
  3. 比较两个数组的第k/2个数，较小的那部分不可能包含第k小的数
  4. 时间复杂度：O(log(m+n))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

class Solution {
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        let total = nums1.count + nums2.count
        
        if total % 2 == 1 {
            return Double(findKth(nums1, 0, nums2, 0, total / 2 + 1))
        } else {
            let left = findKth(nums1, 0, nums2, 0, total / 2)
            let right = findKth(nums1, 0, nums2, 0, total / 2 + 1)
            return Double(left + right) / 2.0
        }
    }
    
    // 在两个有序数组中找第k小的数
    private func findKth(_ nums1: [Int], _ i: Int, _ nums2: [Int], _ j: Int, _ k: Int) -> Int {
        // 如果第一个数组为空或已经用完，直接从第二个数组取第k小的数
        if i >= nums1.count {
            return nums2[j + k - 1]
        }
        // 如果第二个数组为空或已经用完，直接从第一个数组取第k小的数
        if j >= nums2.count {
            return nums1[i + k - 1]
        }
        // 如果k=1，返回两个数组首元素中的较小值
        if k == 1 {
            return min(nums1[i], nums2[j])
        }
        
        // 计算两个数组的第k/2个元素
        // 如果数组长度不足k/2，则取整个数组的最大值
        let mid1 = i + k/2 - 1 < nums1.count ? nums1[i + k/2 - 1] : Int.max
        let mid2 = j + k/2 - 1 < nums2.count ? nums2[j + k/2 - 1] : Int.max
        
        // 比较两个数组的第k/2个元素，较小的那部分不可能包含第k小的数
        if mid1 < mid2 {
            // 排除nums1的前k/2个元素
            return findKth(nums1, i + k/2, nums2, j, k - k/2)
        } else {
            // 排除nums2的前k/2个元素
            return findKth(nums1, i, nums2, j + k/2, k - k/2)
        }
    }
}

// 测试代码
let solution = Solution()
print(solution.findMedianSortedArrays([1,3], [2])) // 输出: 2.0
print(solution.findMedianSortedArrays([1,2], [3,4])) // 输出: 2.5

复杂度分析：

  • 时间复杂度：O(log(m+n))，每次递归都会将问题规模减少一半
  • 空间复杂度：O(log(m+n))，递归调用栈的深度

难点解析：

  1. 理解问题转化：将中位数问题转化为寻找第k小的数
  2. 边界条件处理：处理数组为空或长度不足的情况
  3. 递归终止条件：k=1或某个数组为空时的处理
  4. 排除元素的策略：每次排除k/2个元素，确保不会排除掉第k小的数

优化思路： 还有一种O(log(min(m,n)))的解法，通过在较短的数组上二分查找分割点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

class Solution {
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        // 确保nums1是较短的数组，优化时间复杂度
        if nums1.count > nums2.count {
            return findMedianSortedArrays(nums2, nums1)
        }
        
        let m = nums1.count
        let n = nums2.count
        let totalLeft = (m + n + 1) / 2
        
        // 在nums1上进行二分查找，找到合适的分割点
        var left = 0
        var right = m
        
        while left < right {
            let i = left + (right - left) / 2 // nums1的分割点
            let j = totalLeft - i // nums2的分割点
            
            if nums1[i] < nums2[j-1] {
                // nums1[i]太小，需要增加i
                left = i + 1
            } else {
                // nums1[i]太大或刚好，需要减小i
                right = i
            }
        }
        
        let i = left
        let j = totalLeft - i
        
        // 计算左半部分的最大值和右半部分的最小值
        let maxLeft: Int
        if i == 0 { maxLeft = nums2[j-1] }
        else if j == 0 { maxLeft = nums1[i-1] }
        else { maxLeft = max(nums1[i-1], nums2[j-1]) }
        
        // 如果总数为奇数，中位数就是左半部分的最大值
        if (m + n) % 2 == 1 {
            return Double(maxLeft)
        }
        
        // 如果总数为偶数，还需要计算右半部分的最小值
        let minRight: Int
        if i == m { minRight = nums2[j] }
        else if j == n { minRight = nums1[i] }
        else { minRight = min(nums1[i], nums2[j]) }
        
        // 中位数是左半部分最大值和右半部分最小值的平均值
        return Double(maxLeft + minRight) / 2.0
    }
}

2. 进阶练习

315. 计算右侧小于当前元素的个数

题目描述与示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 输入: [5,2,6,1]
// 输出: [2,1,1,0]

class Solution {
    private var count: [Int] = []
    private var temp: [(Int, Int)] = []
    
    func countSmaller(_ nums: [Int]) -> [Int] {
        count = Array(repeating: 0, count: nums.count)
        temp = Array(repeating: (0, 0), count: nums.count)
        let indexed = nums.enumerated().map { ($1, $0) }
        mergeSort(indexed, 0, nums.count - 1)
        return count
    }
    
    private func mergeSort(_ nums: [(Int, Int)], _ left: Int, _ right: Int) {
        // 实现细节省略...
    }
}

493. 翻转对

题目描述与示例：

1
2
3
4
5
6
7
8
9
10
11
12
13

// 输入: [1,3,2,3,1]
// 输出: 2
// 解释: (3,1), (3,1) 是翻转对

class Solution {
    func reversePairs(_ nums: [Int]) -> Int {
        return mergeSort(nums, 0, nums.count - 1)
    }
    
    private func mergeSort(_ nums: [Int], _ left: Int, _ right: Int) -> Int {
        // 实现细节省略...
    }
}

719. 找出第k小的距离对

题目描述与示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// 输入: nums = [1,3,1], k = 1
// 输出: 0

func smallestDistancePair(_ nums: [Int], _ k: Int) -> Int {
    let sorted = nums.sorted()
    var left = 0
    var right = sorted.last! - sorted.first!
    
    while left < right {
        let mid = left + (right - left) / 2
        if countPairs(sorted, mid) < k {
            left = mid + 1
        } else {
            right = mid
        }
    }
    
    return left
}

786. 第K个最小的素数分数

题目描述与示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// 输入: arr = [1,2,3,5], k = 3
// 输出: [2,5]
// 解释: 分数为 [1/5, 1/3, 2/5, 1/2, 3/5, 2/3]
//      第三小的分数是 2/5

func kthSmallestPrimeFraction(_ arr: [Int], _ k: Int) -> [Int] {
    var left: Double = 0
    var right: Double = 1
    
    while true {
        let mid = (left + right) / 2
        var count = 0
        var maxFraction = 0.0
        var ans = [0, 1]
        
        // 实现细节省略...
    }
}

3. 练习题总结

题号难度关键技术注意点
215中等快速选择partition的实现
33中等二分查找判断有序部分
34中等二分查找边界处理
4困难二分查找时间复杂度要求
69简单二分查找整数溢出
315困难归并排序索引处理
493困难归并排序条件判断
719困难二分答案计数技巧
786困难二分答案精度处理

通过这些练习题，你可以：

  1. 深入理解排序和查找算法的应用场景
  2. 掌握不同的问题解决策略
  3. 提高算法实现的准确性和效率
  4. 学会处理边界情况和特殊输入

69. x的平方根

题目描述： 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例：

1
2
3
4
5
6

输入：x = 4
输出：2

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

解题思路：

  1. 使用二分查找
  2. 注意整数溢出问题，使用除法代替乘法
  3. 最后返回right而不是left的原因是我们要向下取整
  4. 时间复杂度：O(log x)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    func mySqrt(_ x: Int) -> Int {
        // 处理特殊情况
        if x == 0 { return 0 }
        if x <= 3 { return 1 }
        
        var left = 2
        var right = x / 2
        
        while left <= right {
            let mid = left + (right - left) / 2
            
            // 使用除法避免整数溢出
            let quotient = x / mid
            
            if quotient == mid {
                // 找到精确的平方根
                return mid
            } else if quotient < mid {
                // mid太大
                right = mid - 1
            } else {
                // mid太小
                left = mid + 1
            }
        }
        
        // 返回right是因为我们需要向下取整
        // 当循环结束时，left > right，而right是最后一个满足 right*right <= x 的值
        return right
    }
}

// 测试代码
let solution = Solution()
print(solution.mySqrt(4)) // 输出: 2
print(solution.mySqrt(8)) // 输出: 2

优化版本： 可以使用牛顿迭代法求平方根，这种方法收敛速度更快：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {
    func mySqrt(_ x: Int) -> Int {
        if x == 0 { return 0 }
        
        // 牛顿迭代法
        var result = x
        
        while result > x / result {
            result = (result + x / result) / 2
        }
        
        return result
    }
}

复杂度分析：

  • 时间复杂度：
    • 二分查找：O(log x)
    • 牛顿迭代法：O(log x)，但实际上收敛速度更快
  • 空间复杂度：O(1)

易错点：

  1. 整数溢出：计算mid*mid时可能会溢出，应使用除法代替
  2. 边界条件：处理x=0和x=1的特殊情况
  3. 返回值：返回right而不是left，确保向下取整
算法
算法 排序 搜索 数据结构 快速排序 二分查找
本文由作者按照 CC BY 4.0 进行授权