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

Question

我有一个排序的数组,并希望对它进行二进制搜索.

所以我问Swift库中是否已有类似等等的东西？或者是否有可用的独立版本？

当然我可以自己写,但我想避免再次重新发明轮子.

Answer 1

这是我最喜欢的二进制搜索实现.它不仅可用于查找元素,还可用于查找插入索引.通过提供相应的谓词(例如{ $0 < x }vs { $0 > x }vs { $0 <= x }vs { $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

Answer 2

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

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){
    println("Element found on index: \(searchIndex)");
}

Answer 3

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 相同的索引，因此，在没有突变的情况下（如本例），它因此非常高效。

Answer 4

我使用extension的Indexable实现indexOfFirstObjectPassingTest.

• 它接受一个test谓词,并返回第一个元素的索引以通过测试.
• 如果没有这样的索引,则返回endIndex的Indexable.
• 如果Indexable是空的,你就得到了endIndex.

例

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

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

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

重要

你需要确保test在false索引之后永远不会为任何索引返回true.这相当于二进制搜索要求您的数据有序的通常前提条件.

具体来说,你绝不能这样做 a.indexOfFirstObjectPassingTest {$0==3}.这将无法正常工作.

为什么？

indexOfFirstObjectPassingTest是有用的,因为它可以让你找到数据中的东西范围.通过调整测试,您可以找到"东西"的下限和上限.

这是一些数据:

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

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

let firstOf2s = a.indexOfFirstObjectPassingTest({$0>=2})
let endOf2s = a.indexOfFirstObjectPassingTest({$0>2})
let rangeOf2s = firstOf2s..<endOf2s

• 如果2数据中没有s,我们将返回一个空的范围,我们不需要任何特殊处理.
• 如果有2s,我们会找到所有这些.

作为一个例子,我在实现中使用它layoutAttributesForElementsInRect.我UICollectionViewCells的存储垂直排序在一个数组中.编写一对调用很容易,这些调用将查找特定矩形内的所有单元格并排除任何其他单元格.

码

extension Indexable {
  func indexOfFirstObjectPassingTest( test: (Self._Element -> Bool) ) -> Self.Index {
    var searchRange = startIndex..<endIndex

    while searchRange.count > 0 {
      let testIndex: Index = searchRange.startIndex.advancedBy((searchRange.count-1) / 2)
      let passesTest: Bool = test(self[testIndex])

      if(searchRange.count == 1) {
        return passesTest ? searchRange.startIndex : endIndex
      }

      if(passesTest) {
        searchRange.endIndex = testIndex.advancedBy(1)
      }
      else {
        searchRange.startIndex = testIndex.advancedBy(1)
      }
    }

    return endIndex
  }
}

免责声明和谨慎

我有大约6年的iOS经验,10个目标C,以及> 18个编程一般...

......但是我在Swift的第3天:-)

1. 我在Indexable协议上使用了扩展.这可能是愚蠢的做法 - 欢迎反馈.
2. 二进制搜索是出了名的难以正确的代码.你真的应该阅读这个链接,找出它们实现中常见的错误,但这里有一个摘录:

当Jon Bentley在专业程序员的课程中将其作为一个问题时,他发现在经过几个小时的工作后,一个惊人的百分之九十的人无法正确编码二进制搜索,另一项研究表明,只有二十本教科书中的五本.此外,Bentley自己在二十六年出版的"珍珠编程"一书中发表的二元搜索实现包含了一个二十多年未被发现的错误.

鉴于最后一点,这里是测试此代码.他们过去了.它们不太可能是详尽无遗的 - 所以肯定仍然会有错误.测试不保证实际上是正确的!没有测试测试.

测试

class BinarySearchTest: XCTestCase {

  func testCantFind() {
    XCTAssertEqual([].indexOfFirstObjectPassingTest {(_: Int) -> Bool in false}, 0)
    XCTAssertEqual([1].indexOfFirstObjectPassingTest {(_: Int) -> Bool in false}, 1)
    XCTAssertEqual([1,2].indexOfFirstObjectPassingTest {(_: Int) -> Bool in false}, 2)
    XCTAssertEqual([1,2,3].indexOfFirstObjectPassingTest {(_: Int) -> Bool in false}, 3)
    XCTAssertEqual([1,2,3,4].indexOfFirstObjectPassingTest {(_: Int) -> Bool in false}, 4)
  }

  func testAlwaysFirst() {
    XCTAssertEqual([].indexOfFirstObjectPassingTest {(_: Int) -> Bool in true}, 0)
    XCTAssertEqual([1].indexOfFirstObjectPassingTest {(_: Int) -> Bool in true}, 0)
    XCTAssertEqual([1,2].indexOfFirstObjectPassingTest {(_: Int) -> Bool in true}, 0)
    XCTAssertEqual([1,2,3].indexOfFirstObjectPassingTest {(_: Int) -> Bool in true}, 0)
    XCTAssertEqual([1,2,3,4].indexOfFirstObjectPassingTest {(_: Int) -> Bool in true}, 0)
  }

  func testFirstMatch() {
    XCTAssertEqual([1].indexOfFirstObjectPassingTest {1<=$0}, 0)
    XCTAssertEqual([0,1].indexOfFirstObjectPassingTest {1<=$0}, 1)
    XCTAssertEqual([1,2].indexOfFirstObjectPassingTest {1<=$0}, 0)
    XCTAssertEqual([0,1,2].indexOfFirstObjectPassingTest {1<=$0}, 1)
  }

  func testLots() {
    let a = Array(0..<1000)
    for i in a.indices {
      XCTAssertEqual(a.indexOfFirstObjectPassingTest({Int(i)<=$0}), i)
    }
  }
}