Ответ 1

Вот общий способ использования бинарного поиска:

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)");
}

Ответ 2

Здесь моя любимая реализация бинарного поиска. Это полезно не только для поиска элемента, но и для поиска индекса вставки. Подробная информация о предполагаемом порядке сортировки (по возрастанию или по убыванию) и поведении относительно равных элементов контролируется путем предоставления соответствующего предиката (например, { $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

Ответ 3

Я использую 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)
    }
  }
}

Ответ 4

Вот реализация для отсортированного массива строк.

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")) 

Ответ 5

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, с которым он разделяет хранилище, поэтому в отсутствие мутаций (как в этом случае) он поэтому очень эффективен.

Ответ 6

Здесь более эффективная реализация, которая возвращает более одного индекса, если в массиве больше 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
}

}

Ответ 7

Вот полный пример с несколькими тестовыми примерами для 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. Он работает и выполняет двоичный поиск.

Ответ 8

здесь используется двоичный поиск, используя синтаксис

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
}