swift版二分查找(折半查找)

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

二分查找作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围之内,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。废话少说,直接上代码,可复制粘贴直接出结果!

import UIKit

class ViewController: UIViewController {

    let targetNum = 27
    let sourceList: [Int] = [1,13,18,26,27,29,32,33,48,100,277,10000]
    var compareTimes = 0
    
    override func viewDidLoad() {
        super.viewDidLoad()
        let result = binarySearch(targetNum: targetNum, sourceList: sourceList)
        print("搜索结果: \(result)  比较次数 : \(compareTimes)")
    }
    
    func binarySearch(targetNum: Int, sourceList: [Int]) -> Int {
        var start = 0
        var end = sourceList.count - 1
        while start <= end {
            compareTimes += 1
            let minddle = (start + end)/2
            print("----第\(compareTimes)次比较的中值为\(sourceList[minddle])")
            if targetNum == sourceList[minddle] {
                return minddle
            }
            if targetNum < sourceList[minddle] {
                end = minddle - 1
            }
            if targetNum > sourceList[minddle] {
                start = minddle + 1
            }
        }
        return -1
    }

}