[swift-evolution] [Proposal] Add Array binary search to the standard library

[Igor Vasilenko]

Introduction

Right now, for Array implemented array.contains(element) and array.indexOf(element)for searching in an array. Both of these methods iterate over all elements in the array, starting at index 0, until they find a match. In the worst case (there is no match), they have to iterate over the entire array. In big O notation, the methods’ performance characteristic is O(n). This is usually not a problem for small arrays with only a few dozen elements. But if your code regularly needs to find objects in arrays with thousands of elements, you may want to look for a faster search algorithm.

Motivation

If the array is sorted by the search key, binary search can give you a huge boost in performance. By comparing the middle element in the array to the search item, the algorithm effectively halves the number of elements it has to search trough with each iteration. Binary search has O(log n) performance. What does this mean in practice? Searching a sorted array of 100,000 elements using binary search would require at most 17 comparisons compared to the 50,000 comparisons a naive linear search would take on average.

Detailed design

public func binarySearch<T: Comparable>(array: [T], key: T, range: Range<Int>) -> Int? {
    if range.startIndex >= range.endIndex {
        return nil
    } else {
        let midIndex = range.endIndex + (range.endIndex - range.startIndex) / 2
        if array[midIndex] > key {
            return binarySearch(array, key: key, range: range.startIndex ..< midIndex)
        } else if array[midIndex] < key {
            return binarySearch(array, key: key, range: midIndex + 1 ..< range.endIndex)
        } else {
            return midIndex
        }
    }
}

let numbers = [1, 2, 3, 4, 5]
binarySearch(numbers, key: 3, range: 1 ..< numbers.count)
Best regards, Igor Vasilenko 

iOS Developer at Yota

spb.vasilenko at gmail.com <mailto:name.surname at e-legion.com>








-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.swift.org/pipermail/swift-evolution/attachments/20160907/5f258fe2/attachment.html>