算法图解系列之二分查找[01]

1.1 二分查找

// MARK: - 1.1 二分查找
func binarySearch(target: Int, array: Array<Int>) -> Int {
    var low = 0, high = array.count - 1
    var mid: Int, guess: Int
    var cycleCount = 0
    
    while low <= high {
        cycleCount += 1
        
        mid = (low + high) / 2
        guess = array[mid]
        // 相同 返回结果, 并结束循环
        if guess == target {
            print("查找循环: \(cycleCount)")
            return mid
        }else if guess > target {
            high = mid
        }else {
            low = mid
        }
    }
    
    return atNone
}

let counts = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12 ,13 ,14 ,15];
let target = 3

let result = binarySearch(target: target, array: counts)
print("result: \(result)")

1.2 二分查找的运行时间

// MARK: - 1.2 二分查找的运行时间
// FIXME: O(logn)

1.3 大O表示法

// MARK: - 1.3 大O表示法

// FIXME: 1. 大O表示法的单位并不是秒(不是以时间为单位).
// FIXME: 2. 大O表示法是表示时间增速, 表示这个算法的快慢.
// FIXME: 3. 大O表示法指出了最糟糕情况下的运行时间.

1.4 总结

// TODO: - 1.4 总结
// TODO: 1. 算法的速度并非指时间, 而是指操作数的增速.
// TODO: 2. 谈论算法的速度时, 我们说的是随着输入的增加, 其运行时间是以什么样的速度增加.
// TODO: 3. 算法的运行时间用大O表示法表示.
// TODO: 4. O(logn)比O(n)快, 随着搜索元素的增多, 前者比后者快的更多.