<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div class=""><blockquote type="cite" class=""></blockquote><blockquote type="cite" class=""></blockquote><blockquote type="cite" class=""><blockquote type="cite" class="">On Mon Feb 15 2016, Jeff Hajewski <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</blockquote><blockquote type="cite" class=""><br class=""></blockquote><blockquote type="cite" class=""><div class="">I am working on SR-368 <<a href="https://bugs.swift.org/browse/SR-368" class="">https://bugs.swift.org/browse/SR-368</a>> and am hoping to get some feedback from the community.</div></blockquote></blockquote></div><div class=""><br class=""></div><div class="">Definitely +1!</div><div class=""><br class=""></div>Shameless plug:<div class=""><br class=""></div><div class="">I've played with this idea in the past, implementing all of the four suggested binary searches as generic functions over index ranges or collections, using a custom 3-way comparator. The commented code and unit tests are found in <a href="https://github.com/knomi/Allsorts" class="">https://github.com/knomi/Allsorts</a>. The library is also somewhat tested in production.</div><div class=""><br class=""></div><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><div style="margin: 0px; line-height: normal;" class=""><span style="color: rgb(187, 44, 162);" class="">let</span> i: <span style="color: rgb(112, 61, 170);" class="">Int</span> = [<span style="color: rgb(209, 47, 27);" class="">"a"</span>,<span style="color: rgb(209, 47, 27);" class="">"b"</span>,<span style="color: rgb(209, 47, 27);" class="">"c"</span>,<span style="color: rgb(209, 47, 27);" class="">"c"</span>,<span style="color: rgb(209, 47, 27);" class="">"c"</span>,<span style="color: rgb(209, 47, 27);" class="">"d"</span>,<span style="color: rgb(209, 47, 27);" class="">"f"</span>,<span style="color: rgb(209, 47, 27);" class="">"f"</span>].binarySearch(<span style="color: rgb(209, 47, 27);" class="">"c"</span>) <span style="color: rgb(0, 132, 0);" class="">//=> 2, 3 or 4</span></div><div style="margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span> j: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Int</span>? = [<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"a"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"b"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"c"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"c"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"c"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"d"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"f"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"f"</span>].binaryFind(<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"e"</span>) <span style="color: rgb(0, 132, 0);" class="">//=> nil</span></div><div style="margin: 0px; line-height: normal;" class=""><span style="color: rgb(0, 132, 0);" class="">// C</span><span style="color: rgb(0, 132, 0);" class="">ompare values to "e". `a <=> b` performs a 3-way comparison, returning .LT, .EQ or .GT</span></div><div style="margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span> k: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Int</span> = [<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"a"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"b"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"c"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"c"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"c"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"d"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"f"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"f"</span>].lowerBound {x <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">in</span> x <=> <span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"e"</span>} <span style="color: rgb(0, 132, 0);" class="">//=> 6</span></div><div style="margin: 0px; line-height: normal;" class=""><span style="color: rgb(0, 132, 0);" class="">// </span><span style="color: rgb(0, 132, 0);" class="">Reverse order (the arguments of <=> are flipped):</span></div><div style="margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span> r: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Range</span><<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Int</span>> = [<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"e"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"e"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"d"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"c"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"c"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"c"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"b"</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"a"</span>].equalRange {x <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">in</span> <span style="font-variant-ligatures: no-common-ligatures; color: #d12f1b" class="">"c"</span> <=> x} <span style="color: rgb(0, 132, 0);" class="">//=> 3 ..< 6</span></div><div class=""><br class=""></div></div></div><div class="">I'd be happy to join forces in making the algorithms available in the standard library.</div><div class=""><br class=""></div><div class="">I believe that my code tackles many points Dave mentioned:</div><div class=""><br class=""></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class="">(1) You don't need to construct an element just to perform the search. You only need a function to tell if the search should proceed to the left or right, or if there's a match.</div><div class=""><br class=""></div><div class="">(2) You don't really need to a concrete collection either. A <span style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);" class="">Range</span><span style="font-family: Menlo; font-size: 11px;" class=""><</span><span style="font-family: Menlo; font-size: 11px; color: rgb(112, 61, 170);" class="">Int</span><span style="font-family: Menlo; font-size: 11px;" class="">></span> will do just as fine, as long as you're able to say how those indices should be compared to each other (usually by looking up somewhere else).</div><div class=""><br class=""></div><div class="">(3) The collection can be sorted by any comparator (which I call an "<span style="font-family: Menlo; font-size: 11px;" class="">ordering</span>"), as long as you pass that information along as the closure (the <span style="font-family: Menlo; font-size: 11px;" class="">ordering</span>).</div><div class=""><br class=""></div><div class="">(4) I use three-way comparisons to avoid extra work comparing e.g. strings.</div></blockquote><div class=""><ul class=""><ul class=""><li class="">Turns out comparisons defined that way also compose amazingly well, see first examples in README.</li><li class="">There's an operator "<span style="font-family: Menlo; font-size: 11px;" class="">x <=> y</span>" returning <span style="font-family: Menlo; font-size: 11px;" class="">Ordering.LT</span>, <span style="font-family: Menlo; font-size: 11px;" class="">.EQ</span>, or <span style="font-family: Menlo; font-size: 11px;" class="">.GT</span> instead of just <span style="color: rgb(112, 61, 170); font-family: Menlo; font-size: 11px;" class="">Bool</span>. However, that operator has little to do with the implementation of binary search.</li><li class="">(The topic of three-way comparisons <a href="https://lists.swift.org/pipermail/swift-evolution/Week-of-Mon-20160201/009127.html" class="">was discussed earlier</a> in swift-evolution. I think it should find its way into the <span style="color: rgb(112, 61, 170); font-family: Menlo; font-size: 11px;" class="">Comparable</span> protocol directly, as an alternative to defining "<span style="font-family: Menlo; font-size: 11px;" class=""><</span>".)</li></ul></ul></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class="">(5) By convention, I <b class="">do not</b> return <span style="font-family: Menlo; font-size: 11px;" class="">nil</span> just because an index wasn't found. You might still want to use the index for the insertion of new elements. For convenience, there's <span style="font-family: Menlo; font-size: 11px;" class="">binaryFind</span> which is guaranteed to return an index exactly when there's a match, otherwise <span style="font-family: Menlo; font-size: 11px;" class="">nil</span>.</div><div class=""><br class=""></div><div class="">(6) There are convenience overloads for sorted collections of <span style="font-family: Menlo; font-size: 11px;" class="">Generator.Element : </span><span style="color: rgb(112, 61, 170); font-family: Menlo; font-size: 11px;" class="">Comparable</span> so that you can give a <span style="font-family: Menlo; font-size: 11px;" class="">value</span> to look up.</div><div class=""><br class=""></div><div class="">(7) The project also contains more experimental stuff like a working (but slow?) port of libc++'s binary heap algorithms. Over time, those would be nice to port to Swift standard library as well.</div></blockquote><div class=""><br class=""></div><div class="">The existing interface on GitHub is still preferring top-level functions. I'm modernising the interface into the following (plus the usual <span style="color: rgb(187, 44, 162); font-family: Menlo; font-size: 11px;" class="">public</span>, <span style="color: rgb(187, 44, 162); font-family: Menlo; font-size: 11px;" class="">@warn_unused_result</span>, <span style="color: rgb(187, 44, 162); font-family: Menlo; font-size: 11px;" class="">@noescape</span>, <span style="color: rgb(187, 44, 162); font-family: Menlo; font-size: 11px;" class="">throws</span> and <span style="color: rgb(187, 44, 162); font-family: Menlo; font-size: 11px;" class="">rethrows</span> dance). An already working implementation can be found in the <a href="https://github.com/knomi/Allsorts/blob/protocol-extensions/Allsorts/BinarySearch.swift" class="">protocol-extensions branch</a>:</div><div class=""><div class=""><br class=""></div></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">enum</span> Ordering : <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Int</span> { <span style="color: rgb(187, 44, 162);" class="">case</span> LT = -1, EQ, GT } <span style="color: rgb(0, 132, 0);" class="">// NSComparisonResult, basically</span></div></div></div><div class=""><div class=""><br class=""></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(112, 61, 170);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">extension</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span>CollectionType<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">where</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> Index : </span>RandomAccessIndexType<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> {</span></div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <span style="color: rgb(187, 44, 162);" class="">func</span> binaryFind(ordering: Generator.Element -> <span style="color: rgb(79, 129, 135);" class="">Ordering</span>) -> <span style="color: rgb(112, 61, 170);" class="">Self</span>.<span style="color: rgb(112, 61, 170);" class="">Index</span>?</div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <span style="color: rgb(187, 44, 162);" class="">func</span> binarySearch(ordering: Generator.Element -> <span style="color: rgb(79, 129, 135);" class="">Ordering</span>) -> <span style="color: rgb(112, 61, 170);" class="">Self</span>.<span style="color: rgb(112, 61, 170);" class="">Index</span></div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <span style="color: rgb(187, 44, 162);" class="">func</span> lowerBound(ordering: Generator.Element -> <span style="color: rgb(79, 129, 135);" class="">Ordering</span>) -> <span style="color: rgb(112, 61, 170);" class="">Self</span>.<span style="color: rgb(112, 61, 170);" class="">Index</span></div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <span style="color: rgb(187, 44, 162);" class="">func</span> upperBound(ordering: Generator.Element -> <span style="color: rgb(79, 129, 135);" class="">Ordering</span>) -> <span style="color: rgb(112, 61, 170);" class="">Self</span>.<span style="color: rgb(112, 61, 170);" class="">Index</span></div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <span style="color: rgb(187, 44, 162);" class="">func</span> equalRange(ordering: Generator.Element -> <span style="color: rgb(79, 129, 135);" class="">Ordering</span>) -> <span style="color: rgb(112, 61, 170);" class="">Range</span><<span style="color: rgb(112, 61, 170);" class="">Self</span>.<span style="color: rgb(112, 61, 170);" class="">Index</span>></div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">}</div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(112, 61, 170);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">extension</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span>CollectionType<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">where</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> Index : </span>RandomAccessIndexType<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">, Generator.Element : </span>Comparable<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> {</span></div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <span style="color: rgb(187, 44, 162);" class="">func</span> binaryFind(value: <span style="color: rgb(112, 61, 170);" class="">Generator</span>.<span style="color: rgb(112, 61, 170);" class="">Element</span>) -> <span style="color: rgb(112, 61, 170);" class="">Self</span>.<span style="color: rgb(112, 61, 170);" class="">Index</span>?</div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <span style="color: rgb(187, 44, 162);" class="">func</span> binarySearch(value: <span style="color: rgb(112, 61, 170);" class="">Generator</span>.<span style="color: rgb(112, 61, 170);" class="">Element</span>) -> <span style="color: rgb(112, 61, 170);" class="">Self</span>.<span style="color: rgb(112, 61, 170);" class="">Index</span></div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <span style="color: rgb(187, 44, 162);" class="">func</span> lowerBound(value: <span style="color: rgb(112, 61, 170);" class="">Generator</span>.<span style="color: rgb(112, 61, 170);" class="">Element</span>) -> <span style="color: rgb(112, 61, 170);" class="">Self</span>.<span style="color: rgb(112, 61, 170);" class="">Index</span></div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <span style="color: rgb(187, 44, 162);" class="">func</span> upperBound(value: <span style="color: rgb(112, 61, 170);" class="">Generator</span>.<span style="color: rgb(112, 61, 170);" class="">Element</span>) -> <span style="color: rgb(112, 61, 170);" class="">Self</span>.<span style="color: rgb(112, 61, 170);" class="">Index</span></div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <span style="color: rgb(187, 44, 162);" class="">func</span> equalRange(value: <span style="color: rgb(112, 61, 170);" class="">Generator</span>.<span style="color: rgb(112, 61, 170);" class="">Element</span>) -> <span style="color: rgb(112, 61, 170);" class="">Range</span><<span style="color: rgb(112, 61, 170);" class="">Self</span>.<span style="color: rgb(112, 61, 170);" class="">Index</span>></div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">}</div></div></div></blockquote><div class=""><div class=""><br class=""></div><div class=""><blockquote type="cite" class="">On 15 Feb 2016, at 23:34, Dave Abrahams via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</blockquote></div><div class=""><blockquote type="cite" class=""><span id="x-apple-selection:end"></span><br class=""></blockquote><blockquote type="cite" class="">Note that you don't need random access to get an advantage from binary search if the comparison is sufficiently expensive.</blockquote></div><div class=""><div class=""><br class=""></div><div class="">One current restriction is that I only define these functions over collections with random access. What it boils down to is the implementation of <span style="font-family: Menlo; font-size: 11px;" class="">midIndex</span>:</div><div class=""><br class=""></div></div></div><blockquote style="margin: 0 0 0 40px; border: none; padding: 0px;" class=""><div class=""><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><span style="color: rgb(187, 44, 162);" class="">internal</span> <span style="color: rgb(187, 44, 162);" class="">func</span> midIndex<Ix : <span style="color: rgb(112, 61, 170);" class="">RandomAccessIndexType</span>>(range: <span style="color: rgb(112, 61, 170);" class="">Range</span><<span style="color: rgb(112, 61, 170);" class="">Ix</span>>) -> <span style="color: rgb(112, 61, 170);" class="">Ix</span> {</div></div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="color: rgb(187, 44, 162);" class="">let</span> fullDistance = range.<span style="color: rgb(112, 61, 170);" class="">startIndex</span>.<span style="color: rgb(61, 29, 129);" class="">distanceTo</span>(range.<span style="color: rgb(112, 61, 170);" class="">endIndex</span>)</div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> <span style="color: rgb(187, 44, 162);" class="">return</span> range.<span style="color: rgb(112, 61, 170);" class="">startIndex</span>.<span style="color: rgb(61, 29, 129);" class="">advancedBy</span>(fullDistance <span style="color: rgb(61, 29, 129);" class="">/</span> <span style="color: rgb(39, 42, 216);" class="">2</span>)</div></div></div><div class=""><div class=""><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">}</div></div></div></blockquote><div class=""><div class=""><br class=""></div><div class="">That could certainly be written with weaker constraints as well; I just haven't checked how it affects to the interface in terms of duplication of code, and to the performance of the random access version.</div><div class=""><br class=""></div><div class=""><span class="Apple-style-span" style="border-collapse: separate; line-height: normal; border-spacing: 0px;"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-variant: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: -webkit-auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; border-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-stroke-width: 0px; font-size: 12px;"><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">— Pyry Jahkola</div><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""></div></span></div></span></div></div></body></html>