arrays - pseint - busqueda binaria recursiva
Swift: ¿Búsqueda binaria de matriz estándar? (8)
Tengo una matriz ordenada y quiero hacer una búsqueda binaria en ella.
¿Entonces estoy preguntando si algo ya está disponible en la biblioteca de Swift, como por ejemplo? ¿O hay una versión de tipo independiente disponible?
Por supuesto, podría escribirlo por mi cuenta, pero me gusta evitar reinventar la rueda de nuevo.
Aquí está la búsqueda binaria usando la sintaxis
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
}
Aquí está mi implementación favorita de búsqueda binaria. Es útil no solo para encontrar el elemento, sino también para encontrar el índice de inserción. Los detalles sobre el orden de clasificación asumido (ascendente o descendente) y el comportamiento con respecto a elementos iguales se controlan al proporcionar un predicado correspondiente (por ejemplo, { $0 < x } vs { $0 > x } vs { $0 <= x } vs { $0 >= x } ). El comentario dice claramente qué hace exactamente.
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
}
}
Ejemplo de uso:
(0 ..< 778).binarySearch { $0 < 145 } // 145
Aquí hay un ejemplo completo con varios casos de prueba para Swift 3.1. No hay posibilidad de que esto sea más rápido que la implementación predeterminada, pero ese no es el punto. La extensión de la matriz está en la parte inferior:
// 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)
}
}
Esto es bastante casero, así que ... caveat emptor. Funciona y hace búsqueda binaria.
Aquí hay una forma genérica de usar la búsqueda binaria:
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)");
}
Aquí hay una implementación para una matriz ordenada de cadenas.
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"))
Aquí hay una mejor implementación que devuelve más de un índice, si hay más de 1 en la matriz.
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
}
}
Utilizo una extension en Indexable implementando indexOfFirstObjectPassingTest .
- Toma un predicado de
testy devuelve el índice del primer elemento para pasar la prueba. - Si no hay tal índice, entonces devuelve
endIndexdeIndexable. - Si el
Indexableestá vacío, obtienes elendIndex.
Ejemplo
let a = [1,2,3,4]
a.map{$0>=3}
// returns [false, false, true, true]
a.indexOfFirstObjectPassingTest {$0>=3}
// returns 2
Importante
Debe asegurarse de que la test nunca se devuelva en false para ningún índice después de un índice para el que se haya dicho que es true . Esto es equivalente a la condición previa habitual de que la búsqueda binaria requiere que sus datos estén en orden.
Específicamente, no debe hacer a.indexOfFirstObjectPassingTest {$0==3} . Esto no funcionará correctamente.
¿Por qué?
indexOfFirstObjectPassingTest es útil porque le permite encontrar rangos de cosas en sus datos. Al ajustar la prueba, puede encontrar los límites inferior y superior de "cosas".
Aquí hay algunos datos:
let a = [1,1,1, 2,2,2,2, 3, 4, 5]
Podemos encontrar el Range de todos los 2 s así ...
let firstOf2s = a.indexOfFirstObjectPassingTest({$0>=2})
let endOf2s = a.indexOfFirstObjectPassingTest({$0>2})
let rangeOf2s = firstOf2s..<endOf2s
- Si no hay
2s en los datos, recuperaremos un rango vacío y no necesitamos ningún manejo especial. - Siempre que haya
2s, los encontraremos todos.
Como ejemplo, uso esto en una implementación de layoutAttributesForElementsInRect . Mis UICollectionViewCells se almacenan ordenados verticalmente en una matriz. Es fácil escribir un par de llamadas que encuentren todas las celdas que están dentro de un rectángulo en particular y excluyan cualquier otra.
Código
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
}
}
Descargo de responsabilidad y precaución
Tengo alrededor de 6 años de experiencia en iOS, 10 de Objective C y> 18 de programación en general ...
... Pero estoy en el día 3 de Swift :-)
- He utilizado una extensión en el protocolo
Indexable. Esto podría ser un enfoque estúpido - retroalimentación bienvenida. - Las búsquedas binarias son notoriamente difíciles de codificar correctamente. Realmente debería leer ese enlace para averiguar qué tan comunes son los errores en su implementación, pero aquí hay un extracto:
Cuando Jon Bentley lo asignó como un problema en un curso para programadores profesionales, descubrió que un noventa por ciento asombroso no pudo codificar correctamente una búsqueda binaria después de varias horas de trabajo en él, y otro estudio muestra que solo se encuentra un código exacto. Cinco de veinte libros de texto . Además, la propia implementación de Bentley de búsqueda binaria, publicada en su libro Programming Pearls de 1986, contiene un error que no se detectó durante más de veinte años.
Dado ese último punto, aquí están las pruebas para este código. Pasan. Es improbable que sean exhaustivos, por lo que puede haber errores. No se garantiza que las pruebas sean realmente correctas! No hay pruebas para las pruebas.
Pruebas
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)
}
}
}
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)
}
}
Esto es, en mi opinión, muy legible y aprovecha el hecho de que el ArraySlice de Swift es una vista de Array y retiene los mismos índices que el Array original con el que comparte el almacenamiento, por lo que, en ausencia de mutaciones (como en este caso), Es por lo tanto muy eficiente.