Swift：标准数组的二分查找？

Question

我有一个排序好的数组，并想在其上执行二分查找。

所以我想知道Swift库中是否已经有像sort等的功能？或者是否有一种与类型无关的版本可用？

当然，我可以自己编写，但我喜欢避免重复造轮子。

- Peter71

---

我不知道 filter 的速度有多快。它适用于每个数组。但是我知道我的数组已经排序了。因此，我可以使用二进制来提高速度。 - Peter71

你需要“提高速度”吗？这样做是否会有明显的效果？如果没有，就不要让代码变得更加复杂。 - zaph

当然，这就是我转换的原因。我的数组中有超过1,700,000个字符串。而且我还要使用这个搜索功能另外一万次。 - Peter71

如果您使用本页面上的任何实现，值得强调的是，“二分查找”因为“实现问题”而声名狼藉。 我强烈建议为您使用的任何代码编写测试。例如，Java的“Arrays.binarySearch（）”在SDK 6.0版本之前是有问题的。作为对我的回答的宣传，它包括了测试。 - Benjohn

如果您想检查完整的算法存储库或检查特定的二分搜索，请访问Swift Algorithms Club存储库https://github.com/raywenderlich/swift-algorithm-club/blob/master/Binary%20Search/BinarySearch.swift - Barbara R

Answer 1

这是我最喜欢的二分查找实现方法。它不仅可以用于查找元素，还可以用于查找插入位置。关于假定排序顺序（升序或降序）和相等元素的行为细节由提供相应谓词（例如{ $0 < x }与{ $0 > x }与{ $0 <= x }与{ $0 >= x }）控制。注释清楚地说明了它确切的功能。

extension RandomAccessCollection {
    /// Finds such index N that predicate is true for all elements up to
    /// but not including the index N, and is false for all elements
    /// starting with index N.
    /// Behavior is undefined if there is no such N.
    func binarySearch(predicate: (Element) -> Bool) -> Index {
        var low = startIndex
        var high = endIndex
        while low != high {
            let mid = index(low, offsetBy: distance(from: low, to: high)/2)
            if predicate(self[mid]) {
                low = index(after: mid)
            } else {
                high = mid
            }
        }
        return low
    }
}

使用示例：

(0 ..< 778).binarySearch { $0 < 145 } // 145

- Vadim Yelagin

---

Swift 3版本已发布在https://dev59.com/ypvga4cB1Zd3GeqP9OgZ。 - Martin R

这应该是对“RandomAccessCollection”的扩展，而不是“Collection”。此扩展仅能保证O(n log n)的复杂度。 - taylor swift

对集合进行下标操作的时间复杂度始终为O(1)，但是通过K来偏移索引的时间复杂度为O(K)。因此，对于集合的这个扩展，总体复杂度为O(N)（因为N/2 + N/4 + N/8 + ... + 1）。对于RandomAccessCollection，时间复杂度为O(logN)，因为偏移操作的时间复杂度为O(1)。 - Vadim Yelagin

VadimYelagin，你和@taylorswift在这个问题上是不是有分歧或者意见一致？很抱歉让大家等待这么久，谢谢大家。 - Dan Rosenstark

泰勒·斯威夫特绝对是正确的，这个算法只保证随机访问集合的O(logN)复杂度，而不是任意集合。然而，导致这种情况的具体原因并不完全正确，因此我觉得有必要澄清以避免评论中进一步的混淆。 - Vadim Yelagin

Answer 2

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

- Daniel Krom

---

如果没有匹配项，不返回-1会更好。更符合Swift的方式是返回一个可选类型。另一个好方法是在未找到元素时返回endIndex。 - Benjohn

@Benjohn 完全同意可选项，答案已经两年了，是时候编辑一下了 :) - Daniel Krom

它也可以应用于字符串吗？ - Jeff Bootsholz

@RajuyourPepe 用于符合 Comparable 协议的类。 - Twitter khuong291

你应该在开头添加 guard !inputArr.isEmpty else { return nil } 以处理空数组情况。此外，我认为 else if 条件应该是 lowerIndex >= upperIndex。 - Morpheus

Answer 3

我在RandomAccessCollection上使用一个extension，实现了bisectToFirstIndex(where:)方法，并且接受一个谓词。

• 它接受一个test谓词，并返回第一个通过测试的元素的索引。
• 如果没有这样的索引，则返回nil。
• 如果Collection为空，则返回nil。

示例

let a = [1,2,3,4]

a.map{$0>=3}
// returns [false, false, true, true]

a.bisectToFirstIndex {$0>=3}
// returns 2

重要

您需要确保test在一个索引之后，对于任何索引都不会返回false。这相当于二分查找所需的数据顺序预处理。

具体来说，您不能执行a.bisectToFirstIndex {$0==3}。这样做将无法正常工作。

为什么？

bisectToFirstIndex 很有用，因为它可以让您查找数据范围。通过调整测试，您可以找到“stuff”的下限和上限。

以下是一些数据：

let a = [1,1,1, 2,2,2,2, 3, 4, 5]

我们可以这样找到所有 2 的 Range...

let firstOf2s = a.bisectToFirstIndex { $ 0>= 2 }
let endOf2s = a.bisectToFirstIndex { $0 > 2 }
let rangeOf2s = firstOf2s ..< endOf2s

示例应用

我在实现layoutAttributesForElementsInRect时使用了这个。我的UICollectionViewCells以垂直方向排序存储在一个数组中。很容易编写一对调用来查找所有位于特定矩形内的单元格并排除其他单元格。

代码

extension RandomAccessCollection {
    
    public func bisectToFirstIndex(where predicate: (Element) throws -> Bool) rethrows -> Index? {
        var intervalStart = startIndex
        var intervalEnd = endIndex
        
        while intervalStart != intervalEnd {
            let intervalLength = distance(from: intervalStart, to: intervalEnd)
            
            guard intervalLength > 1 else {
                return try predicate(self[intervalStart]) ? intervalStart : nil
            }
            
            let testIndex = index(intervalStart, offsetBy: (intervalLength - 1) / 2)
            
            if try predicate(self[testIndex]) {
                intervalEnd = index(after: testIndex)
            }
            else {
                intervalStart = index(after: testIndex)
            }
        }
        
        return nil
    }
}

更新…

这里的实现扩展了RandomAccessCollection，我已经更新了代码以与当前的Swift版本（5或其他版本）兼容。

二分查找注意事项

二分查找是编写正确的代码极其困难。您真的应该阅读该链接，以了解实现中常见错误有多么普遍，以下是其中一段摘录：

当Jon Bentley将其指定为专业程序员课程中的一个问题时，他发现在几个小时的工作后，惊人的90％未能正确编写二分查找代码，并且另一项研究表明，在20本教科书中只有五本有正确的二分查找代码。此外，Bentley自己的二分查找实现，发表于他1986年的书《Programming Pearls》中，包含一个错误，在20多年内一直未被发现。

鉴于上述最后一点，这里有一个针对此代码的测试。它通过了！测试并不详尽-因此可能仍然存在错误。

测试

final class Collection_BisectTests: XCTestCase {

    func test_bisect() {
        for length in 0...100 {
            let collection = 0 ... length
            let targets = -4 ... length + 4
            
            for toFind in targets {
                let bisectIndex = collection.bisectToFirstIndex { $0 > toFind }
                let expectIndex = collection.firstIndex { $0 > toFind }
                XCTAssertEqual(bisectIndex, expectIndex, "Finding \(toFind+1) in 0...\(length)")
            }
        }
    }
}

- Benjohn

---

非常感谢您详细的答案和解释。我在Swift 2.x文档中阅读到了“Indexable”的内容：“重要提示：在大多数情况下，最好忽略此协议并改用CollectionType，因为它具有更完整的接口。”所以根据Vadim的答案，我使用了extension CollectionType where Index: RandomAccessIndexType。另外，我想知道是否值得并且可能通过在while之前对（self）进行排序来保证这一点。 - AJP

嗨@ajp，感谢您的想法。1.我对Swift标准库不熟悉（仍然！），但通常情况下，我会使用最小的接口来支持所需的功能。2.我理解您的担忧，但我建议不要提前排序。排序（在大多数情况下）是一个O(n.log(n))操作。二分查找是一个O(log(n))操作。如果您正在使用二分查找，则可能需要那个（巨大的）渐近性能差异。如果您不需要该差异，则最好使用完全不同的算法来处理无序数据。 - Benjohn

谢谢 @Benjohn，明白了，很好的逻辑。 - AJP

字符串版本怎么样？ - Jeff Bootsholz

嘿 @AJP - 我更新到现代的 Swift，并像你6年前建议的那样使其符合 RandomAccessCollection :-) - Benjohn

Answer 4

extension ArraySlice where Element: Comparable {
    func binarySearch(_ value: Element) -> Int? {
        guard !isEmpty else { return nil }

        let midIndex = (startIndex + endIndex) / 2
        if value == self[midIndex] {
            return midIndex
        } else if value > self[midIndex] {
            return self[(midIndex + 1)...].binarySearch(value)
        } else {
            return self[..<midIndex].binarySearch(value)
        }
    }
}

extension Array where Element: Comparable {
    func binarySearch(_ value: Element) -> Int? {
        return self[0...].binarySearch(value)
    }
}

在我看来，这段代码非常易读，并且利用了Swift的ArraySlice是Array上的视图并保留与原始Array相同的索引的特点。由于没有改变(就像在这种情况下一样)，因此非常高效。

- Alessandro Martin

Answer 5

这是使用while语法的二分查找

func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
    var lowerBound = 0
    var upperBound = a.count
    while lowerBound < upperBound {
        let midIndex = lowerBound + (upperBound - lowerBound) / 2
        if a[midIndex] == key {
            return midIndex
        } else if a[midIndex] < key {
            lowerBound = midIndex + 1
        } else {
            upperBound = midIndex
        }
    }
    return nil
}

- Lucy Jeong

Answer 6

这是一个关于字符串排序数组的实现。

var arr = ["a", "abc", "aabc", "aabbc", "aaabbbcc", "bacc", "bbcc", "bbbccc", "cb", "cbb", "cbbc", "d" , "defff", "deffz"]

func binarySearch(_ array: [String], value: String) -> String {

    var firstIndex = 0
    var lastIndex = array.count - 1
    var wordToFind = "Not founded"
    var count = 0

    while firstIndex <= lastIndex {

        count += 1
        let middleIndex = (firstIndex + lastIndex) / 2
        let middleValue = array[middleIndex]

        if middleValue == value {
            wordToFind = middleValue
            return wordToFind
        }
        if value.localizedCompare(middleValue) == ComparisonResult.orderedDescending {
            firstIndex = middleIndex + 1
        }
        if value.localizedCompare(middleValue) == ComparisonResult.orderedAscending {
            print(middleValue)
            lastIndex = middleIndex - 1
        }
    }
    return wordToFind
}
//print d
print(binarySearch(arr, value: "d")) 

- James Rochabrun

Answer 7

以下是如何在Swift 5中创建二分查找函数，本示例假设您要查找的项目已保证在列表中，但如果您的项目不保证在列表中，则可以先运行此代码进行检查：

yourList.contains(yourItem) //will return true or false

这是二分查找函数：

override func viewDidLoad() {
    super.viewDidLoad()
    
    print(binarySearch(list: [1, 2, 4, 5, 6], num: 6)) //returns 4
}

func binarySearch(list: [Int], num: Int) -> Int //returns index of num
{
    var firstIndex = 0
    var lastIndex = list.count - 1
    
    var middleIndex = (firstIndex + lastIndex) / 2
    var middleValue = list[middleIndex]
    
    while true //loop until we find the item we are looking for
    {
        middleIndex = (firstIndex + lastIndex) / 2 //getting the list's middle index
        middleValue = list[middleIndex]
        
        if middleValue > num
        {
            lastIndex = middleIndex - 1 //get the left side of the remaining list
        }
        else if middleValue < num
        {
            firstIndex = middleIndex + 1 //get the right side of the remaining list
        }
        else if middleValue == num
        { 
            break //found the correct value so we can break out of the loop
        }
    }
    return middleIndex
}

我制作了一段YouTube视频，在这里讲解了这个问题。

- Aryaa Sk

Answer 8

为了完整起见，这里提供一种完全基于模式匹配的实现：

extension Collection where Element: Comparable {
    func binarySearch(for element: Element) -> Index? {
        switch index(startIndex, offsetBy: distance(from: startIndex, to: endIndex) / 2) {
        case let i where i >= endIndex: return nil
        case let i where self[i] == element: return i
        case let i where self[i] > element: return self[..<i].binarySearch(for: element)
        case let i: return self[index(after: i)..<endIndex].binarySearch(for: element)
        }
    }
}

上述代码应适用于任何类型的集合，无论是切片还是非切片，零偏移或非零偏移。

- Cristik

Answer 9

另一种实现方式：如果您希望使您的结构体或类可搜索，但不想将它们设为 Comparable，则可以将它们设为 BinarySearchable：

public protocol BinarySearchable {
    associatedtype C: Comparable
    var searchable: C { get }
}


public extension Array where Element: BinarySearchable {

    func binarySearch(_ prefix: Element.C) -> Index {
        var low = 0
        var high = count
        while low != high {
            let mid = (low + high) / 2
            if self[mid].searchable < prefix {
                low = mid + 1
            } else {
                high = mid
            }
        }
        return low
    }
}

一个应该按照 name 进行排序和搜索的结构体的示例用法：

struct Country: BinraySearchable {
    var code: String
    var name: String

    var searchable: String { name }
}

// Suppose you have a list of countries sorted by `name`, you want to find
// the index of the first country whose name starts with "United", others
// will follow:

let index = listOfCountries.binarySearch("United")

- mojuba

---

BinarySearchable 类型是无意义的，你可以直接使用 Comparable。 - user187676

@ErikAigner，只要搜索键不是对象本身，就不能这样做。比如说你有一个带有id的对象，想要按照id排序和搜索，但是数组存储的是整个对象。你需要分别定义你的“可搜索”属性和一个独立的BinarySearchable协议。 - mojuba

这样，您可以通过一个属性来搜索一个对象，并且只能扩展它一次，因此只能使一个对象可搜索。如果直接使用Comparable，则可以将存储的对象包装在一个实现所需比较行为的struct中。 - user187676

@ErikAigner 我知道，但仅通过一个属性使对象可比较可能是不可取甚至危险的 - 想想意外的比较。二分搜索是非常特定的功能，我更喜欢将这种类型的比较限制在其中。 - mojuba

Answer 10

这里有一个更好的实现，如果数组中有多个索引，则返回多个索引。

extension Array where Element: Comparable {

/* Array Must be sorted */

func binarySearch(key: Element) -> [Index]? {
    return self.binarySearch(key, initialIndex: 0)
}

private func binarySearch(key: Element, initialIndex: Index) -> [Index]? {

    guard count > 0 else { return nil }

    let midIndex = count / 2
    let midElement = self[midIndex]

    if key == midElement {

        // Found!

        let foundIndex = initialIndex + midIndex

        var indexes = [foundIndex]

        // Check neighbors for same values

        // Check Left Side

        var leftIndex = midIndex - 1

        while leftIndex >= 0 {

            //While there is still more items on the left to check

            print(leftIndex)

            if self[leftIndex] == key {

                //If the items on the left is still matching key

                indexes.append(leftIndex + initialIndex)
                leftIndex--

            } else {

                // The item on the left is not identical to key

                break
            }
        }

        // Check Right side

        var rightIndex = midIndex + 1

        while rightIndex < count {

            //While there is still more items on the left to check

            if self[rightIndex] == key {

                //If the items on the left is still matching key

                indexes.append(rightIndex + initialIndex)
                rightIndex++

            } else {

                // The item on the left is not identical to key

                break
            }
        }

        return indexes.sort{ return $0 < $1 }
    }

    if count == 1 {

        guard let first = first else { return nil }

        if first == key {
            return [initialIndex]
        }
        return nil
    }


    if key < midElement {

        return Array(self[0..<midIndex]).binarySearch(key, initialIndex: initialIndex + 0)
    }

    if key > midElement {

        return Array(self[midIndex..<count]).binarySearch(key, initialIndex: initialIndex + midIndex)
    }

    return nil
}

}

- Jacky Wang