二分查找

这是一个 Swift 模块，用于在已排序的集合中进行二分查找。它支持搜索现有元素以及插入索引。还有其他选项可以指定您是搜索第一个、最后一个还是任何匹配的索引。

要求

Swift 4 或更高版本
iOS 8.0+ 或 macOS 10.11+

注意

以下所有方法都假定 Collection 已排序。在未排序的 Collection 上调用这些方法的结果是未定义的。

基本用法

如果 Collection 的元素符合 Comparable 协议，则用法非常简单

let sortedArray = [3,5,7,7,9]

// Search for the index of an existing element:

if let index = sortedArray.binary(search: 5) {

	print("The index is \(index)") // 1

} else {

	print("Not found.")
}

// Search for the insertion index:

let insertionIndex = sortedArray.binaryInsertion(search: 6)
print("insertionIndex: \(insertionIndex)") // 2

如果需要，您可以指定当数组包含一系列匹配索引时应返回哪个索引

let sortedArray = [3,5,7,7,9]
let index = sortedArray.binary(search: 7, position: .last) // 3
let insertionIndex = sortedArray.binaryInsertion(search: 7, position: .last) // 4

对于元素不符合 Comparable 的集合，您必须指定一个比较块

struct Person {

	let name: String
	
	init(_ name: String) {

		self.name = name
	}
}

let persons: [Person] = [Person("Lucy Diamonds"), Person("Joe Schmoe")]

let index = persons.binary(search: Person("Lucy Diamonds"), comparator: { (person1, person2) -> ComparisonResult in

	if person1.name < person2.name {
		return .orderedAscending
	}
	if person1.name > person2.name {
		return .orderedDescending
	}
	return .orderedSame
})