我有一个排序好的数组,并想在其上执行二分查找。
所以我想知道Swift库中是否已经有像sort等的功能?或者是否有一种与类型无关的版本可用?
当然,我可以自己编写,但我喜欢避免重复造轮子。
我有一个排序好的数组,并想在其上执行二分查找。
所以我想知道Swift库中是否已经有像sort等的功能?或者是否有一种与类型无关的版本可用?
当然,我可以自己编写,但我喜欢避免重复造轮子。
这是我最喜欢的二分查找实现方法。它不仅可以用于查找元素,还可以用于查找插入位置。关于假定排序顺序(升序或降序)和相等元素的行为细节由提供相应谓词(例如{ $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
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)")
}
-1
会更好。更符合Swift的方式是返回一个可选类型。另一个好方法是在未找到元素时返回endIndex
。 - BenjohnComparable
协议的类。 - Twitter khuong291guard !inputArr.isEmpty else { return nil }
以处理空数组情况。此外,我认为 else if 条件应该是 lowerIndex >= upperIndex
。 - Morpheus我在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)")
}
}
}
}
CollectionType
,因为它具有更完整的接口。”所以根据Vadim的答案,我使用了extension CollectionType where Index: RandomAccessIndexType
。另外,我想知道是否值得并且可能通过在while
之前对(self)进行排序来保证这一点。 - AJPO(n.log(n))
操作。二分查找是一个O(log(n))
操作。如果您正在使用二分查找,则可能需要那个(巨大的)渐近性能差异。如果您不需要该差异,则最好使用完全不同的算法来处理无序数据。 - BenjohnRandomAccessCollection
:-) - Benjohnextension 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相同的索引的特点。由于没有改变(就像在这种情况下一样),因此非常高效。
这是使用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
}
这是一个关于字符串排序数组的实现。
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"))
以下是如何在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视频,在这里讲解了这个问题。
为了完整起见,这里提供一种完全基于模式匹配的实现:
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)
}
}
}
另一种实现方式:如果您希望使您的结构体或类可搜索,但不想将它们设为 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")
BinarySearchable
类型是无意义的,你可以直接使用 Comparable
。 - user187676Comparable
,则可以将存储的对象包装在一个实现所需比较行为的struct
中。 - user187676extension 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
}
}