<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="">I’m not sure the documentation matches the .lowerBound() and .upperBound() behaviours accurately enough; it suggests that a bound will be found for a predicate “match”, however if my predicate is { $0 == foo } then these won’t actually work at all unless I get lucky and the middle element is a match, to me this means that they will only work with comparison predicates such as { $0 > foo }, but in that case the lower bound is for the first element that is not greater than foo, but I wouldn’t call it a “match” until I can also test it for equality.</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">I’ve been doing some work recently on a sorted collection and I implemented a binary search a bit differently. My method returns the nearest index given an isOrderedBefore predicate, returning .endIndex if nothing matches. Implementation below:</div><div class=""><br class=""></div><div class=""><div style="margin: 0px; font-size: 11px; font-family: Menlo; color: rgb(187, 44, 162);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""><span class="Apple-tab-span" style="white-space:pre"> </span></span>@warn_unused_result</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span class="Apple-tab-span" style="white-space:pre"> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">public</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">func</span> binarySearch(withinRange theRange:<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Range</span><<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Index</span>>?=<span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">nil</span>, isOrderedBefore:(<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Generator</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Bool</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Index</span> {</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span class="Apple-tab-span" style="white-space:pre"> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">var</span> low:<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Index</span>, high:<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Index</span></div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span class="Apple-tab-span" style="white-space:pre"> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">if</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span> theSpecifiedRange = theRange { low = theSpecifiedRange.startIndex; high = theSpecifiedRange.endIndex }</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span class="Apple-tab-span" style="white-space:pre"> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">else</span> { low = <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">self</span>.startIndex; high = <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">self</span>.endIndex }</div><p style="margin: 0px; font-size: 11px; font-family: Menlo; min-height: 13px;" class=""><span class="Apple-tab-span" style="white-space:pre"> </span><br class="webkit-block-placeholder"></p><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span class="Apple-tab-span" style="white-space:pre"> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">while</span> low != high {</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span class="Apple-tab-span" style="white-space:pre"> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span> mid = low.advancedBy(low.distanceTo(high) / <span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">2</span>)</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span class="Apple-tab-span" style="white-space:pre"> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">if</span> isOrderedBefore(<span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">self</span>[mid]) { low = mid.successor() }</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span class="Apple-tab-span" style="white-space:pre"> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">else</span> { high = mid }</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span class="Apple-tab-span" style="white-space:pre"> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">return</span> low</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><span class="Apple-tab-span" style="white-space:pre"> </span>}</div></div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""><br class=""></div>What this gives me is really an insertion index, however I can implement searching for a specific element like so:<div class=""><div style="margin: 0px; font-size: 11px; font-family: Menlo; min-height: 13px;" class=""><div style="margin: 0px; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; color: rgb(112, 61, 170);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> isOrderedBefore:(</span>Generator<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">.</span>Element<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">, </span>Generator<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">.</span>Element<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">) -> </span>Bool</div></div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">func</span> indexOf(theElement:<span style="color: rgb(112, 61, 170);" class="">Equatable</span>) -> <span style="color: rgb(112, 61, 170);" class="">Index</span>? {</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span> theNearestIndex = <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">self</span>.binarySearch(){ <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">self</span>.isOrderedBefore($0, theElement) }</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">if</span> theNearestIndex < <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">self</span>.endIndex && <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">self</span>[theNearestIndex] == theElement { <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">return</span> theNearestIndex }</div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">return</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">nil</span></div><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> }</div></div><div class=""><br class=""></div><div class="">I can also do things like a generic insert() method like so:</div><div class=""><br class=""></div><div class=""><div style="margin: 0px; font-size: 11px; font-family: Menlo;" class=""> <span style="color: rgb(187, 44, 162);" class="">func</span> insert(theElement:<span style="color: rgb(112, 61, 170);" class="">Comparable</span>) { <span style="color: rgb(187, 44, 162);" class="">self</span>.insert(theElement, atIndex: <span style="color: rgb(187, 44, 162);" class="">self</span>.binarySearch(){ <span style="color: rgb(187, 44, 162);" class="">self</span>.isOrderedBefore($0, theElement) }) }</div></div><div class=""><br class=""></div><div class="">(note I’ve simplified these as examples as they won’t go into CollectionType as-is, it’s just to give you the idea).</div><div class=""><br class=""></div><div class="">Anyway, it seems to me that this enables simple matching of both an exact element and the lower bound (this is what the .indexOf() above should return), while also giving a useful value if the element isn’t found, though it does require testing the result to be sure. When it comes to matching a specific element, the above actually eliminates tests for equality during the search, only having to test once at the end to confirm the result is a match.</div><div class=""><br class=""></div><div class="">I also added a variable starting range, as I had to handle merging two sorted collections, in which case it’s useful to restrict the search range as you go since there’s no point revisiting indices that you’ve passed already if the elements are sorted properly.</div><div class=""><br class=""></div><div class="">The above can also perform an upper bound search by passing in a predicate such as { $0 <= foo }, though in that case you’re performing all the extra comparisons <b class="">plus</b> a check at the end, so there might still be an argument for two methods, e.g nearestLowerBound() and nearestUpperBound().</div><div class=""><br class=""></div><div class=""><br class=""></div><div class="">Lastly, in my case I’ve defined the above method on CollectionType directly, rather than requiring Comparable; since it takes a predicate its only requirement is the collection is sorted prior to search it. In fact, constraining the method to Comparable doesn’t guarantee that the collection is sorted, only that its elements can be compared in isolation.</div><div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On 15 Mar 2016, at 14:28, Lorenzo Racca 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=""><meta http-equiv="Content-Type" content="text/html charset=utf-8" class=""><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Hi all, <div class=""><br class=""></div><div class="">Using the library for an app with wide sorted arrays I’ve found out that Swift doesn’t (yet) have binary search functions.</div><div class="">Standing on the fact that C++, Java and .NET all have Binary Search functions in their standard libs, and given the notorious difficulty to create the algorithm (hence the need of developers to trust the library function) I’m proposing to adopt these. </div><div class="">I worked out some code, recalling the C++ functions binary_search, lower_bound and upper_bound. </div><div class="">I’ve tested them and they seem all right. </div><div class=""><br class=""></div><div class="">Also, they all return the `Index` of a found element (say, in an Array), so that they can be implemented to return either a boolean value, or the element itself. They either return nil or -1 if not any or if the predicate isn’t matched, but they all could surely be arranged to return nil.</div><div class="">The code for binarySearch is : </div><div class=""><span style="font-family: Menlo; font-size: 11px; color: rgb(187, 44, 162);" class=""><br class=""></span></div><div class=""><span style="font-family: Menlo; font-size: 11px; color: rgb(187, 44, 162);" class="">extension</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="">CollectionType</span><span style="font-family: Menlo; font-size: 11px;" class=""> </span><span style="font-family: Menlo; font-size: 11px; color: rgb(187, 44, 162);" class="">where</span><span style="font-family: Menlo; font-size: 11px;" class=""> Generator.Element : Comparable {</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>/// Returns `element.Index` if `element` is in `self`.</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>/// If `element` is not in `self`, returns nil.</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(187, 44, 162);" class=""><span style="" class=""> </span>@warn_unused_result</div><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="">public</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">func</span> binarySearch(element: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Generator</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Index</span>? {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></div><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="">var</span> left = <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">startIndex</span></div><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="">var</span> right = <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">endIndex</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></div><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="">while</span> (left != right) {</div><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="">let</span> mid = left.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">advancedBy</span>(left.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">distanceTo</span>(right) <span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">/</span> <span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">2</span>)</div><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="">let</span> value = <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">self</span>[mid]</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></div><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="">if</span> (value <span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">==</span> element) {</div><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="">return</span> mid</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><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="">if</span> (value <span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class=""><</span> element) {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> left = mid.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">advancedBy</span>(<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">1</span>)</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><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="">if</span> (value <span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">></span> element) {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> right = mid</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><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="">return</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">nil</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">}</div><div class=""><br class=""></div><div class="">lowerBound and upperBound:</div><div class=""><br class=""></div><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="">extension</span> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">CollectionType</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">where</span> Generator.Element : Comparable {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>/// Returns the Index of the smallest element in collection matching `predicate`.</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>/// If none, returns -1.</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(187, 44, 162);" class=""><span style="" class=""> </span>@warn_unused_result</div><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="">func</span> lowerBound(predicate: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Generator</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span> -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Bool</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Index</span> {</div><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="">var</span> result = <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">self</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">startIndex</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">advancedBy</span>(-<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">1</span>)</div><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="">var</span> low = <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">self</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">startIndex</span></div><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="">var</span> hi = <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">self</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">endIndex</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></div><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="">while</span> low != hi {</div><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="">let</span> mid = low.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">advancedBy</span>(low.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">distanceTo</span>(hi) <span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">/</span> <span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">2</span>)</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></div><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="">if</span> predicate(<span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">self</span>[mid]) {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> result = mid</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> hi = mid</div><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="">else</span> {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> low = mid.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">advancedBy</span>(<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">1</span>)</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><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="">return</span> result</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">}</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><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="">extension</span> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">CollectionType</span> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">where</span> Generator.Element : Comparable {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>/// Returns the Index of the biggest element in collection matching `predicate`.</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(0, 132, 0);" class=""><span style="" class=""> </span>/// If none, returns -1.</div><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="">func</span> upperBound(predicate: <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Generator</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Element</span> -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Bool</span>) -> <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Index</span> {</div><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="">var</span> result = <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">startIndex</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">advancedBy</span>(-<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">1</span>)</div><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="">var</span> low = <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">startIndex</span></div><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="">var</span> hi = <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">endIndex</span></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></div><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="">while</span> low != hi {</div><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="">let</span> mid = low.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">advancedBy</span>(low.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">distanceTo</span>(hi) <span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">/</span> <span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">2</span>)</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></div><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="">if</span> predicate(<span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">self</span>[mid]) {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> result = mid</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> low = mid.<span style="font-variant-ligatures: no-common-ligatures; color: #3d1d81" class="">advancedBy</span>(<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">1</span>)</div><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="">else</span> {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> hi = mid</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><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="">return</span> result</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class="">}</div></div><div class=""><br class=""></div><div class="">If you wish to try them, usage is :</div><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="">var</span> array : <span style="font-variant-ligatures: no-common-ligatures; color: #703daa" class="">Array</span> = [<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">1</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">2</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">3</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">4</span>,<span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">5</span>]</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""><br class=""></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><div style="margin: 0px; line-height: normal; color: rgb(0, 132, 0);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span><span style="" class=""> a = </span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">array</span><span style="" class="">.</span><span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">upperBound</span><span style="" class="">{$0 < </span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">3</span><span style="" class="">} </span>//array[a] = 2</div><div style="margin: 0px; line-height: normal;" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">let</span> b = <span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">array</span>.<span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">lowerBound</span>{$0 > <span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">3</span>} <span style="font-variant-ligatures: no-common-ligatures; color: #008400" class="">//array[b] = 4</span></div></div></div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""><br class=""></div><div class="">What do you think? Should I commit a new file to proposals?</div><div class="">Should they be added to CollectionType or SequenceType?</div><div class="">It’s obviously open to discussion and change.</div><div class=""><br class=""></div><div class="">Thank you. </div><div class=""><br class=""></div><div class="">Best, </div><div class=""><br class=""></div><div class=""><div class="">
Lorenzo Racca<br class="">+39 345 9294756<br class=""><a href="mailto:lorenzo.racca@live.it" class="">lorenzo.racca@live.it</a><br class=""><br class="">
</div>
<br class=""></div></div>_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class="">https://lists.swift.org/mailman/listinfo/swift-evolution<br class=""></div></blockquote></div><br class=""></div></body></html>