In my mind, caller should be guarantee that array is sorted. As an example, in Objective-C SDK, NSArray should be is sorted before for using binary search method. But this is a good idea to make a SortedArray. Best regards, Igor Vasilenko
iOS Developer at Yota +7 (999) 527 - 07 - 59 [email protected] <mailto:[email protected]> www.spbvasilenko.github.io <http://www.e-legion.com/> > On 07 Sep 2016, at 12:08, Charlie Monroe <[email protected]> wrote: > > 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 >> <[email protected] <mailto:[email protected]>> 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 >> >> [email protected] <mailto:[email protected]> >> >> >> >> >> >> >> >> >> _______________________________________________ >> swift-evolution mailing list >> [email protected] <mailto:[email protected]> >> https://lists.swift.org/mailman/listinfo/swift-evolution >
_______________________________________________ swift-evolution mailing list [email protected] https://lists.swift.org/mailman/listinfo/swift-evolution
