<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="">Bringing up this topic because it became relevant with Brent Royal-Gordon's "<a href="http://thread.gmane.org/gmane.comp.lang.swift.evolution/15180" class="">[Idea] Bringing the partial/total ordering distinction into Comparable</a><span style="font-family: 'Helvetica Neue';" class="">".</span><div class=""><font face="Helvetica Neue" class=""><br class=""></font></div><div class=""><font face="Helvetica Neue" class="">If the `</font><font face="Menlo" class=""><span style="font-size: 11px;" class=""><=></span></font><font face="Helvetica Neue" class="">` operator with a return type of a three-case `</font><font face="Menlo" class=""><span style="font-size: 11px;" class=""><b class="">enum</b> Order</span></font><font face="Helvetica Neue" class="">`, you can fully define the most generic versions of binary searches as:</font></div><div class=""><font face="Helvetica Neue" class=""><br class=""></font></div><div class=""><font face="Menlo" class=""><span style="font-size: 11px;" class=""> lowerBound(compare: Self.Collection.Element -> Order) -> Index</span></font></div><div class=""><font face="Helvetica Neue" class=""><br class=""></font></div><div class=""><font face="Helvetica Neue" class="">etc.<br class=""></font><div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On 29 Mar 2016, at 13:43, Jeff Hajewski via swift-evolution <<a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" style="font-family: Helvetica; font-size: 13px; font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;" class=""><div class="">I've responded below, but just for the sake of being explicit, this is roughly </div><div class="">the signature for lowerBound, upperBound, and binarySearch I have in </div><div class="">mind based on your comments of a unary predicate:</div><div class=""><br class=""></div><div class="">lowerBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index</div><div class="">upperBound(isOrderedBelow: Self.Collection.Element -> Bool) -> Index</div><div class="">binarySearch(isOrderedBelow: Self.Collection.Element -> Bool) -> Bool<br class=""><div class="gmail_extra"><br class=""></div><div class="gmail_extra">That'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 class=""></div><div class="gmail_extra">let binaryPred = { $0 < $1 }</div><div class="gmail_extra">let unnaryPred = binaryPred($0, value)</div><div class="gmail_extra"><br class=""></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'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 class=""></div></div><div class="">You're right, there's no way a <font face="Menlo" class=""><span style="font-size: 11px;" class="">Bool</span></font>-returning unary comparator could allow you to implement anything but lowerBound. With a three-value result, however, you've got all you need.</div><div class=""><br class=""></div><div class="">I've shamelessly plugged before but for the sake of proving a point, I'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" class="">https://github.com/knomi/Allsorts/blob/master/Allsorts/BinarySearch.swift</a></div><div class=""><br class=""></div><div class="">— Pyry</div></body></html>