<div dir="ltr">Thanks for bringing this back into the spotlight Pyry. A few of us have been working on this issue here:<div><br></div><div><a href="https://github.com/lorenzoracca/Swift-binary-search">https://github.com/lorenzoracca/Swift-binary-search</a><br></div><div><br></div><div>However we have sort of stalled as we have been unable to come up with a unary approach that Dave suggested using just Bool return values. And of course, as you say, the three case order enum would make this a trivial problem.</div><div><br></div><div>I guess the question is, do we move forward without a unary implementation and update if/when we get a three case Order enum or do we wait on a three case Order enum and implement a fully generic version once?</div><div><br></div><div> Jeff</div></div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Apr 28, 2016 at 7:36 AM, Pyry Jahkola <span dir="ltr">&lt;<a href="mailto:pyry.jahkola@iki.fi" target="_blank">pyry.jahkola@iki.fi</a>&gt;</span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word">Bringing up this topic because it became relevant with Brent Royal-Gordon&#39;s &quot;<a href="http://thread.gmane.org/gmane.comp.lang.swift.evolution/15180" target="_blank">[Idea] Bringing the partial/total ordering distinction into Comparable</a><span style="font-family:&#39;Helvetica Neue&#39;">&quot;.</span><div><font face="Helvetica Neue"><br></font></div><div><font face="Helvetica Neue">If the `</font><font face="Menlo"><span style="font-size:11px">&lt;=&gt;</span></font><font face="Helvetica Neue">` operator with a return type of a three-case `</font><font face="Menlo"><span style="font-size:11px"><b>enum</b> Order</span></font><font face="Helvetica Neue">`, you can fully define the most generic versions of binary searches as:</font></div><div><font face="Helvetica Neue"><br></font></div><div><font face="Menlo"><span style="font-size:11px">    lowerBound(compare: Self.Collection.Element -&gt; Order) -&gt; Index</span></font></div><div><font face="Helvetica Neue"><br></font></div><div><font face="Helvetica Neue">etc.<br></font><div><br><div><blockquote type="cite"><div>On 29 Mar 2016, at 13:43, Jeff Hajewski via swift-evolution &lt;<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>&gt; wrote:</div><br><div><div dir="ltr" style="font-family:Helvetica;font-size:13px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px"><div>I&#39;ve responded below, but just for the sake of being explicit, this is roughly </div><div>the signature for lowerBound, upperBound, and binarySearch I have in </div><div>mind based on your comments of a unary predicate:</div><div><br></div><div>lowerBound(isOrderedBelow: Self.Collection.Element -&gt; Bool) -&gt; Index</div><div>upperBound(isOrderedBelow: Self.Collection.Element -&gt; Bool) -&gt; Index</div><div>binarySearch(isOrderedBelow: Self.Collection.Element -&gt; Bool) -&gt; Bool<br><div class="gmail_extra"><br></div><div class="gmail_extra">That&#39;s the general structure - the key is that the exact same predicate is</div><div class="gmail_extra">used in all signatures. The predicate would be defined along the lines of</div><div class="gmail_extra">a binary predicate where one of the parameters is fixed as the search value.</div><div class="gmail_extra">The unary predicate could be formed along the lines of:</div><div class="gmail_extra"><br></div><div class="gmail_extra">let binaryPred = { $0 &lt; $1 }</div><div class="gmail_extra">let unnaryPred = binaryPred($0, value)</div><div class="gmail_extra"><br></div><div class="gmail_extra">where value is the search value. The main point of illustrating that is that</div><div class="gmail_extra">once the unary predicate is defined, we can&#39;t change the position of the</div><div class="gmail_extra">search value within the predicate like they do in the C++ implementation.</div></div></div></div></blockquote></div><br></div></div><div>You&#39;re right, there&#39;s no way a <font face="Menlo"><span style="font-size:11px">Bool</span></font>-returning unary comparator could allow you to implement anything but lowerBound. With a three-value result, however, you&#39;ve got all you need.</div><div><br></div><div>I&#39;ve shamelessly plugged before but for the sake of proving a point, I&#39;ll do it once more: I think this little library we did works as a good starting point for a stdlib binary search API: <a href="https://github.com/knomi/Allsorts/blob/master/Allsorts/BinarySearch.swift" target="_blank">https://github.com/knomi/Allsorts/blob/master/Allsorts/BinarySearch.swift</a></div><span class="HOEnZb"><font color="#888888"><div><br></div><div>— Pyry</div></font></span></div></blockquote></div><br></div>