[Proposal] Add Array binary search to the standard library


(Igor Vasilenko) #1

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@gmail.com <mailto:name.surname@e-legion.com>


(Haravikk) #2

I don't think this is really a problem, just needs to be clear that behaviour is undefined if the array wasn't previously sorted (or not in the same order).

On this topic there was a previous proposal that was undergoing refinements after being initially rejected, you can find it here:
https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md

···

On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution <swift-evolution@swift.org> 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…


(Charlie Monroe) #3

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@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@gmail.com <mailto:name.surname@e-legion.com>

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Guillaume DIDIER) #4

Basically for a binary search to work it needs to operate on a sorted array (it is a necessary invariant).

It is really interesting when you make a lot of search in the same sorted array, hence I would +1 the sorted array, with initializer from an array.

Guillaume DIDIER

···


ÉCOLE POLYTECHNIQUE
91128 PALAISEAU CEDEX
M. +33 (0)7 70 43 18 40
guillaume.didier@polytechnique.edu <mailto:guillaume.didier@polytechnique.edu?subject=>
www.polytechnique.edu <http://www.polytechnique.edu/>

Le 7 sept. 2016 à 12:04, Haravikk via swift-evolution <swift-evolution@swift.org> a écrit :

On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution <swift-evolution@swift.org> 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…

I don't think this is really a problem, just needs to be clear that behaviour is undefined if the array wasn't previously sorted (or not in the same order).

On this topic there was a previous proposal that was undergoing refinements after being initially rejected, you can find it here:
https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Igor Vasilenko) #5

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
spb.vasilenko@gmail.com <mailto:name.surname@e-legion.com>
www.spbvasilenko.github.io <http://www.e-legion.com/>

···

On 07 Sep 2016, at 12:08, Charlie Monroe <charlie@charliemonroe.net> 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 <swift-evolution@swift.org <mailto:swift-evolution@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@gmail.com <mailto:name.surname@e-legion.com>

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution


(Igor Vasilenko) #6

This is mean that my PR/proposal will be as duplicate previous rejected proposal?
Or my proposal have a good chance for accept?
Best regards, Igor Vasilenko

iOS Developer at Yota

+7 (999) 527 - 07 - 59
spb.vasilenko@gmail.com <mailto:name.surname@e-legion.com>
www.spbvasilenko.github.io <http://www.e-legion.com/>

···

On 07 Sep 2016, at 13:04, Haravikk <swift-evolution@haravikk.me> wrote:

On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution <swift-evolution@swift.org> 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…

I don't think this is really a problem, just needs to be clear that behaviour is undefined if the array wasn't previously sorted (or not in the same order).

On this topic there was a previous proposal that was undergoing refinements after being initially rejected, you can find it here:
https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md


(Igor Vasilenko) #7

do you mean this?
public func binarySearch<T: Comparable>(array: [T], key: T, range: Range<Int>, sorted: Bool) -> Int?
Best regards, Igor Vasilenko

iOS Developer at Yota

+7 (999) 527 - 07 - 59
spb.vasilenko@gmail.com <mailto:name.surname@e-legion.com>
www.spbvasilenko.github.io <http://www.e-legion.com/>

···

On 07 Sep 2016, at 13:08, Guillaume DIDIER <guillaume.didier.2014@polytechnique.org> wrote:

Basically for a binary search to work it needs to operate on a sorted array (it is a necessary invariant).

It is really interesting when you make a lot of search in the same sorted array, hence I would +1 the sorted array, with initializer from an array.

Guillaume DIDIER

ÉCOLE POLYTECHNIQUE
91128 PALAISEAU CEDEX
M. +33 (0)7 70 43 18 40
guillaume.didier@polytechnique.edu <mailto:guillaume.didier@polytechnique.edu?subject=>
www.polytechnique.edu <http://www.polytechnique.edu/>

Le 7 sept. 2016 à 12:04, Haravikk via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> a écrit :

On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> 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…

I don't think this is really a problem, just needs to be clear that behaviour is undefined if the array wasn't previously sorted (or not in the same order).

On this topic there was a previous proposal that was undergoing refinements after being initially rejected, you can find it here:
https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Xiaodi Wu) #8

Hi Igor,

Since your proposal would be additive, it probably wouldn't be considered
for review until the next phase of Swift evolution.

My read of the core team's feedback is that some binary search
functionality is welcome, but it's a question of *how* it's designed. When
purely additive changes are in scope, a successful proposal will likely
address the weaknesses of the previous proposal. Since that proposal
considered as an alternative a design such as yours, but it concluded that
a different design was better, you'll probably want to address why you
think this API design is best, or alternatively, you may want to study the
alternatives presented in that proposal and refine them to be better.

···

On Wed, Sep 7, 2016 at 05:16 Igor Vasilenko via swift-evolution < swift-evolution@swift.org> wrote:

do you mean this?

public func binarySearch<T: Comparable>(array: [T], key: T, range: Range<Int>, sorted: Bool) -> Int?

Best regards, Igor Vasilenko

iOS Developer at Yota

+7 (999) 527 - 07 - 59
spb.vasilenko@gmail.com <name.surname@e-legion.com>
www.spbvasilenko.github.io <http://www.e-legion.com/>

On 07 Sep 2016, at 13:08, Guillaume DIDIER < > guillaume.didier.2014@polytechnique.org> wrote:

Basically for a binary search to work it needs to operate on a sorted
array (it is a necessary invariant).

It is really interesting when you make a lot of search in the same sorted
array, hence I would +1 the sorted array, with initializer from an array.

*Guillaume DIDIER*

*ÉCOLE POLYTECHNIQUE*
91128 PALAISEAU CEDEX
M. +33 (0)7 70 43 18 40
guillaume.didier@polytechnique.edu
<guillaume.didier@polytechnique.edu?subject=>
www.polytechnique.edu

Le 7 sept. 2016 à 12:04, Haravikk via swift-evolution < > swift-evolution@swift.org> a écrit :

On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution < > swift-evolution@swift.org> 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…

I don't think this is really a problem, just needs to be clear that
behaviour is undefined if the array wasn't previously sorted (or not in the
same order).

On this topic there was a previous proposal that was undergoing
refinements after being initially rejected, you can find it here:

https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Dave Abrahams) #9

Hi Igor,

Since your proposal would be additive, it probably wouldn't be considered
for review until the next phase of Swift evolution.

My read of the core team's feedback is that some binary search
functionality is welcome, but it's a question of *how* it's designed. When
purely additive changes are in scope, a successful proposal will likely
address the weaknesses of the previous proposal. Since that proposal
considered as an alternative a design such as yours, but it concluded that
a different design was better, you'll probably want to address why you
think this API design is best, or alternatively, you may want to study the
alternatives presented in that proposal and refine them to be better.

+1 to all that. Also, this is not Array-specific; it applies to any
random-access collection at least, and arguably to any collection at
all.

···

on Wed Sep 07 2016, Xiaodi Wu <swift-evolution@swift.org> wrote:

On Wed, Sep 7, 2016 at 05:16 Igor Vasilenko via swift-evolution < > swift-evolution@swift.org> wrote:

do you mean this?

public func binarySearch<T: Comparable>(array: [T], key: T, range: Range<Int>, sorted: Bool) -> Int?

Best regards, Igor Vasilenko

iOS Developer at Yota

+7 (999) 527 - 07 - 59
spb.vasilenko@gmail.com <name.surname-nvfCEkAOCAdWk0Htik3J/w@public.gmane.org>
www.spbvasilenko.github.io <http://www.e-legion.com/>

On 07 Sep 2016, at 13:08, Guillaume DIDIER < >> guillaume.didier.2014@polytechnique.org> wrote:

Basically for a binary search to work it needs to operate on a sorted
array (it is a necessary invariant).

It is really interesting when you make a lot of search in the same sorted
array, hence I would +1 the sorted array, with initializer from an array.

*Guillaume DIDIER*

*ÉCOLE POLYTECHNIQUE*
91128 PALAISEAU CEDEX
M. +33 (0)7 70 43 18 40
guillaume.didier@polytechnique.edu
<guillaume.didier@polytechnique.edu?subject=>
www.polytechnique.edu

Le 7 sept. 2016 à 12:04, Haravikk via swift-evolution < >> swift-evolution@swift.org> a écrit :

On 7 Sep 2016, at 10:08, Charlie Monroe via swift-evolution < >> swift-evolution@swift.org> 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…

I don't think this is really a problem, just needs to be clear that
behaviour is undefined if the array wasn't previously sorted (or not in the
same order).

On this topic there was a previous proposal that was undergoing
refinements after being initially rejected, you can find it here:

https://github.com/apple/swift-evolution/blob/master/proposals/0074-binary-search.md
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
-Dave