Swift:标准数组的二进制搜索? [英] Swift: Binary search for standard array?

问题描述

我有一个已排序的数组，想对其进行二分查找.

I have a sorted array and want to do binary search on it.

所以我想问一下 Swift 库中是否已经提供了诸如 sort 之类的东西?或者有没有类型独立的版本?

So I'm asking if something is already available in Swift library like sort etc.? Or is there a type independend version available?

当然我可以自己写，但我喜欢避免重新发明轮子.

Of course I could write it by my own, but I like to avoid reinventing the wheel again.

推荐答案

这是使用二分查找的通用方法:

Here's a generic way to use binary search:

func binarySearch<T:Comparable>(_ inputArr:Array<T>, _ searchItem: T) -> Int? {
    var lowerIndex = 0
    var upperIndex = inputArr.count - 1

    while (true) {
        let currentIndex = (lowerIndex + upperIndex)/2
        if(inputArr[currentIndex] == searchItem) {
            return currentIndex
        } else if (lowerIndex > upperIndex) {
            return nil
        } else {
            if (inputArr[currentIndex] > searchItem) {
                upperIndex = currentIndex - 1
            } else {
                lowerIndex = currentIndex + 1
            }
        }
    }
}

var myArray = [1,2,3,4,5,6,7,9,10]
if let searchIndex = binarySearch(myArray, 5) {
    print("Element found on index: \(searchIndex)")
}

这篇关于Swift:标准数组的二进制搜索?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！