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

[Charlie Monroe]

Aside from this being additive (i.e. out of scope for Swift 4), this requires the array to be sorted in order for the search to work - who will guarantee this? The caller? What happens when this is called on an array that is not sorted? You likely get nil, while the item is in the array (false negative).

This would probably make sense by not extending Array itself, but introducing SortedArray which would automatically keep its members sorted instead - this way there would be a guarantee that the array is sorted and the user won't have to deal with sorting the array. It would however be at the cost of O(log N) for insertion...

> On Sep 7, 2016, at 10:59 AM, Igor Vasilenko via swift-evolution <swift-evolution at swift.org> wrote:
> 
> 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>
> 
> 
> 
> 
> 
> 
> 
> 
> _______________________________________________
> swift-evolution mailing list
> swift-evolution at swift.org
> https://lists.swift.org/mailman/listinfo/swift-evolution

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