查找

折半查找

  1. 复杂度：O(logn)

  2. 对象：排序的数组

  3. 内容：

    • 设置高低指针
    • 中间开始，如果值相等则结束
    • 值不相等，高低指针向中间迫近
    • 指针相遇，结束

  4. 实现

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

    func BinarySearch(arr []int, goal int) int {
    // 取高低索引
    low, high := 0, len(arr)-1
    // 指针未相遇的时候循环
    for low <= high {
        mid := low + (high-low)>>1
        midV := arr[mid]
        // 符合条件，返回索引
        if midV == goal {
            return mid
        }
        // 不符合条件，高低指针向中间迫近
        if midV < goal {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

排序

快速排序

x s

插入排序