小编典典

Swift:二进制搜索标准数组?

swift

我有一个排序的数组,想要对它进行二进制搜索。

所以我想问一下Swift库中是否已有诸如sort等的东西?还是有类型独立版本可用?

当然,我可以自己编写它,但是我想避免再次发明轮子。


阅读 348

收藏
2020-07-07

共1个答案

小编典典

这是使用二进制搜索的通用方法:

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)")
}
2020-07-07