У меня есть отсортированный массив и вы хотите выполнить его двоичный поиск.
Итак, я спрашиваю, есть ли что-то в библиотеке Swift, например, сортировка и т.д.? Или доступна версия независимого типа?
Конечно, я мог бы написать это самостоятельно, но мне больше не нужно снова изобретать колесо.
Вот общий способ использования бинарного поиска:
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)");
}
Здесь моя любимая реализация бинарного поиска. Это полезно не только для поиска элемента, но и для поиска индекса вставки. Подробная информация о предполагаемом порядке сортировки (по возрастанию или по убыванию) и поведении относительно равных элементов контролируется путем предоставления соответствующего предиката (например, { $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
Я использую extension on 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, мы вернем пустой диапазон, и нам не нужна специальная обработка.2 s, мы найдем все из них.В качестве примера я использую это в реализации 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 из Objective C и программирования 18 вообще...
... Но я нахожусь на 3-м дне Свифта: -)
Indexable. Это может быть глупый подход - приветствуется обратная связь.Когда Джон Бентли назначил его проблемой в курсе для профессиональных программистов, он обнаружил, что поразительно девяносто процентов не смогли правильно закодировать бинарный поиск после нескольких часов работы над ним, а в другом исследовании показано, что точный код поскольку он найден только в пяти из двадцати учебников. Кроме того, собственная реализация Bentley бинарного поиска, опубликованная в его книге 1986 года "Программирование жемчуга", содержит ошибку, которая оставалась незамеченной более двадцати лет.
Учитывая эту последнюю точку, вот тест для этого кода. Они проходят. Они вряд ли будут исчерпывающими - так что, безусловно, могут быть ошибки. Тесты не гарантируются на самом деле правильно! Нет тестов для тестов.
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)
}
}
}
Вот реализация для отсортированного массива строк.
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"))
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, с которым он разделяет хранилище, поэтому в отсутствие мутаций (как в этом случае) он поэтому очень эффективен.
Здесь более эффективная реализация, которая возвращает более одного индекса, если в массиве больше 1.
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
}
}
Вот полный пример с несколькими тестовыми примерами для Swift 3.1. Нет никаких шансов, что это быстрее, чем реализация по умолчанию, но это не так. Расширение массива находится внизу:
// BinarySearchTests.swift
// Created by Dan Rosenstark on 3/27/17
import XCTest
@testable import SwiftAlgos
class BinarySearchTests: XCTestCase {
let sortedArray : [Int] = [-25, 1, 2, 4, 6, 8, 10, 14, 15, 1000]
func test5() {
let traditional = sortedArray.index(of: 5)
let newImplementation = sortedArray.indexUsingBinarySearch(of: 5)
XCTAssertEqual(traditional, newImplementation)
}
func testMembers() {
for item in sortedArray {
let traditional = sortedArray.index(of: item)
let newImplementation = sortedArray.indexUsingBinarySearch(of: item)
XCTAssertEqual(traditional, newImplementation)
}
}
func testMembersAndNonMembers() {
for item in (-100...100) {
let traditional = sortedArray.index(of: item)
let newImplementation = sortedArray.indexUsingBinarySearch(of: item)
XCTAssertEqual(traditional, newImplementation)
}
}
func testSingleMember() {
let sortedArray = [50]
for item in (0...100) {
let traditional = sortedArray.index(of: item)
let newImplementation = sortedArray.indexUsingBinarySearch(of: item)
XCTAssertEqual(traditional, newImplementation)
}
}
func testEmptyArray() {
let sortedArray : [Int] = []
for item in (0...100) {
let traditional = sortedArray.index(of: item)
let newImplementation = sortedArray.indexUsingBinarySearch(of: item)
XCTAssertEqual(traditional, newImplementation)
}
}
}
extension Array where Element : Comparable {
// self must be a sorted Array
func indexUsingBinarySearch(of element: Element) -> Int? {
guard self.count > 0 else { return nil }
return binarySearch(for: element, minIndex: 0, maxIndex: self.count - 1)
}
private func binarySearch(for element: Element, minIndex: Int, maxIndex: Int) -> Int? {
let count = maxIndex - minIndex + 1
// if there are one or two elements, there is no futher recursion:
// stop and check one or both values (and return nil if neither)
if count == 1 {
return element == self[minIndex] ? minIndex : nil
} else if count == 2 {
switch element {
case self[minIndex]: return minIndex
case self[maxIndex]: return maxIndex
default: return nil
}
}
let breakPointIndex = Int(round(Double(maxIndex - minIndex) / 2.0)) + minIndex
let breakPoint = self[breakPointIndex]
let splitUp = (breakPoint < element)
let newMaxIndex : Int = splitUp ? maxIndex : breakPointIndex
let newMinIndex : Int = splitUp ? breakPointIndex : minIndex
return binarySearch(for: element, minIndex: newMinIndex, maxIndex: newMaxIndex)
}
}
Это довольно самодельный, так что... остерегайтесь emptor. Он работает и выполняет двоичный поиск.
здесь используется двоичный поиск, используя синтаксис
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
}