<div dir="ltr">This is something I've been working on as well. The issue I've been stuck on is how we define the predicate and match the definitions of lower_bound and upper_bound from C++. It seems to me that the focus should be on these implementations, since once we have these a simple binary_search follows. Specifically, the issue I'm encountering at the moment is handling `!predicate`. If `predicate` is sorting on a rule like $0 < 3, for example, then the complement is $0 >= 3, which has the effect of creating an upper bound inclusive of 3. To be consistent with the C++ implementation, the upper bound should be strictly greater than 3. In C++ they are able to get around this issue by swapping the indices within the `comp` function (our `predicate`) to eliminate the equality case (e.g., looking at `comp(i,j)` and `comp(j,i)`). I don't see a way to easily do this in our case if we want keep `predicate` of the form `Generator.Element -> Bool`.<div><br></div><div>The following implementations are as far as I've gotten so far.</div><div><br></div><div><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(112,61,170)"><span style="color:rgb(187,44,162)">extension</span><span style="color:rgb(0,0,0)"> </span>CollectionType<span style="color:rgb(0,0,0)"> {</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(123,44,214)"> /// Returns an index such that each element at or above the index is partitioned from below by the partition predicate</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><font color="#000000"><span style="white-space:pre-wrap"> </span></font><span style="color:rgb(123,44,214)">///</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><font color="#000000"><span style="white-space:pre-wrap"> </span></font><span style="color:rgb(123,44,214)">/// - <span style="color:rgb(123,35,170)">Parameter</span> partitionPredicate: The partioning predicate returns `true` for elements in the collection that are</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><font color="#000000"><span style="white-space:pre-wrap"> </span></font><span style="color:rgb(123,44,214)">/// ordered below, with respet to the partitioning predicate.</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(123,44,214)"> /// - <span style="color:rgb(123,35,170)">Complexity</span>: O(lg(n))</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(123,44,214)"> ///</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><font color="#000000"><span style="white-space:pre-wrap"> </span></font><span style="color:rgb(123,44,214)">/// - <span style="color:rgb(123,35,170)">Returns</span>: An index such that each element at or above the returned index evaluates as `false` with respect to `partitionPredicate(_:)`</span></p><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><font color="#000000"><span style="white-space:pre-wrap"> </span></font><span style="color:rgb(187,44,162)">@warn_unused_result</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">func</span> lowerBound(<span style="color:rgb(187,44,162)">@noescape</span> partitionPredicate: <span style="color:rgb(112,61,170)">Self</span>.<span style="color:rgb(112,61,170)">Generator</span>.<span style="color:rgb(112,61,170)">Element</span> -> <span style="color:rgb(112,61,170)">Bool</span>) -> <span style="color:rgb(112,61,170)">Index</span> {</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">var</span> len = <span style="color:rgb(187,44,162)">self</span>.startIndex.distanceTo(<span style="color:rgb(187,44,162)">self</span>.endIndex)</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">var</span> firstIndex = <span style="color:rgb(187,44,162)">self</span>.startIndex</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">while</span> len > <span style="color:rgb(39,42,216)">0</span> {</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">let</span> half = len/<span style="color:rgb(39,42,216)">2</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">let</span> middle = firstIndex.advancedBy(half)</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">if</span> partitionPredicate(<span style="color:rgb(187,44,162)">self</span>[middle]) {</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> firstIndex = middle.advancedBy(<span style="color:rgb(39,42,216)">1</span>)</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> len -= half + <span style="color:rgb(39,42,216)">1</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> } <span style="color:rgb(187,44,162)">else</span> {</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> len = half</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">return</span> firstIndex</p><p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="white-space:pre-wrap"> </span>}</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"><span style="white-space:pre-wrap"> </span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><font color="#000000"><span style="white-space:pre-wrap"> </span></font><span style="color:rgb(123,44,214)">/// Returns an index such that each element below the index is strictly less than the partition predicate</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><font color="#000000"><span style="white-space:pre-wrap"> </span></font><span style="color:rgb(123,44,214)">///</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(123,44,214)"> /// - <span style="color:rgb(123,35,170)">Parameter</span> partitionPredicate: The partioning predicate. Returns `true` for elements in the collection that are</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(123,44,214)"> /// ordered below, with respet to the partitioning predicate.</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><font color="#000000"><span style="white-space:pre-wrap"> </span></font><span style="color:rgb(123,44,214)">/// - <span style="color:rgb(123,35,170)">Complexity</span>: O(lg(n))</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(123,44,214)"> ///</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><font color="#000000"><span style="white-space:pre-wrap"> </span></font><span style="color:rgb(123,44,214)">/// - <span style="color:rgb(123,35,170)">Returns</span>: An index such that each element evaluates as `false` with respect to `partitionPredicate(_:)`</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><font color="#000000"><span style="white-space:pre-wrap"> </span></font><span style="color:rgb(187,44,162)">@warn_unused_result</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="white-space:pre-wrap"> </span><span style="color:rgb(187,44,162)">func</span> upperBound(<span style="color:rgb(187,44,162)">@noescape</span> partitionPredicate:<span style="color:rgb(112,61,170)">Self</span>.<span style="color:rgb(112,61,170)">Generator</span>.<span style="color:rgb(112,61,170)">Element</span> -> <span style="color:rgb(112,61,170)">Bool</span>) -> <span style="color:rgb(112,61,170)">Index</span> {</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">var</span> len = <span style="color:rgb(187,44,162)">self</span>.startIndex.distanceTo(<span style="color:rgb(187,44,162)">self</span>.endIndex)</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">var</span> firstIndex = <span style="color:rgb(187,44,162)">self</span>.startIndex</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">while</span> len > <span style="color:rgb(39,42,216)">0</span> {</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">let</span> half = len/<span style="color:rgb(39,42,216)">2</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">let</span> middle = firstIndex.advancedBy(half)</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">if</span> !partitionPredicate(<span style="color:rgb(187,44,162)">self</span>[middle]) {</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> len = half</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> } <span style="color:rgb(187,44,162)">else</span> {</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> firstIndex = middle.advancedBy(<span style="color:rgb(39,42,216)">1</span>)</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> len -= half + <span style="color:rgb(39,42,216)">1</span></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">return</span> firstIndex</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="white-space:pre-wrap"> </span>}</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> </p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(123,44,214)"><span style="color:rgb(0,0,0)"> </span>/// Returns `true` if element is in Collection, `false` otherwise</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(187,44,162)"><span style="color:rgb(0,0,0)"> </span>@warn_unused_result</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">func</span> binarySearch(<span style="color:rgb(187,44,162)">@noescape</span> partitionPredicate:<span style="color:rgb(112,61,170)">Self</span>.<span style="color:rgb(112,61,170)">Generator</span>.<span style="color:rgb(112,61,170)">Element</span> -> <span style="color:rgb(112,61,170)">Bool</span>) -> <span style="color:rgb(112,61,170)">Bool</span> {</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:rgb(187,44,162)">let</span> lb = lowerBound(partitionPredicate)</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(209,47,27)"><span style="color:rgb(34,34,34)"> </span><span style="color:rgb(187,44,162)">return</span><span style="color:rgb(34,34,34)"> (lb != </span><span style="color:rgb(187,44,162)">self</span><span style="color:rgb(34,34,34)">.endIndex) && !partitionPredicate(</span><span style="color:rgb(187,44,162)">self</span><span style="color:rgb(34,34,34)">[lb])</span><br></p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> </p>
<p style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo">}</p><div><br></div><div>Again, `upperBound` isn't working like it should, mainly because I'm looking at the complement of `predicate`. The only way I see getting around this is making `predicate` take the form `(Generator.Element, Generator.Element) -> Bool`, but this comes at the cost of some added complexity on the user end as you can't simply pass a closure like `{ $0 < 3 }`. I suspect there is an easy solution here and I'm just having a mental block...</div><div><br></div><div>Jeff</div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Mar 15, 2016 at 11:37 AM, Haravikk via swift-evolution <span dir="ltr"><<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>></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"><div>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><br></div><div><br></div><div>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><br></div><div><div style="margin:0px;font-size:11px;font-family:Menlo;color:rgb(187,44,162)"><span style="color:#000000"><span style="white-space:pre-wrap"> </span></span>@warn_unused_result</div><div style="margin:0px;font-size:11px;font-family:Menlo"><span style="white-space:pre-wrap"> </span><span style="color:#bb2ca2">public</span> <span style="color:#bb2ca2">func</span> binarySearch(withinRange theRange:<span style="color:#703daa">Range</span><<span style="color:#703daa">Index</span>>?=<span style="color:#bb2ca2">nil</span>, isOrderedBefore:(<span style="color:#703daa">Generator</span>.<span style="color:#703daa">Element</span>) -> <span style="color:#703daa">Bool</span>) -> <span style="color:#703daa">Index</span> {</div><div style="margin:0px;font-size:11px;font-family:Menlo"><span style="white-space:pre-wrap"> </span><span style="color:#bb2ca2">var</span> low:<span style="color:#703daa">Index</span>, high:<span style="color:#703daa">Index</span></div><div style="margin:0px;font-size:11px;font-family:Menlo"><span style="white-space:pre-wrap"> </span><span style="color:#bb2ca2">if</span> <span style="color:#bb2ca2">let</span> theSpecifiedRange = theRange { low = theSpecifiedRange.startIndex; high = theSpecifiedRange.endIndex }</div><div style="margin:0px;font-size:11px;font-family:Menlo"><span style="white-space:pre-wrap"> </span><span style="color:#bb2ca2">else</span> { low = <span style="color:#bb2ca2">self</span>.startIndex; high = <span style="color:#bb2ca2">self</span>.endIndex }</div><p style="margin:0px;font-size:11px;font-family:Menlo;min-height:13px"><span style="white-space:pre-wrap"> </span><br></p><div style="margin:0px;font-size:11px;font-family:Menlo"><span style="white-space:pre-wrap"> </span><span style="color:#bb2ca2">while</span> low != high {</div><div style="margin:0px;font-size:11px;font-family:Menlo"><span style="white-space:pre-wrap"> </span><span style="color:#bb2ca2">let</span> mid = low.advancedBy(low.distanceTo(high) / <span style="color:#272ad8">2</span>)</div><div style="margin:0px;font-size:11px;font-family:Menlo"><span style="white-space:pre-wrap"> </span><span style="color:#bb2ca2">if</span> isOrderedBefore(<span style="color:#bb2ca2">self</span>[mid]) { low = mid.successor() }</div><div style="margin:0px;font-size:11px;font-family:Menlo"><span style="white-space:pre-wrap"> </span><span style="color:#bb2ca2">else</span> { high = mid }</div><div style="margin:0px;font-size:11px;font-family:Menlo"><span style="white-space:pre-wrap"> </span>}</div><div style="margin:0px;font-size:11px;font-family:Menlo"><span style="white-space:pre-wrap"> </span><span style="color:#bb2ca2">return</span> low</div><div style="margin:0px;font-size:11px;font-family:Menlo"><span style="white-space:pre-wrap"> </span>}</div></div><div style="margin:0px;font-size:11px;font-family:Menlo"><br></div>What this gives me is really an insertion index, however I can implement searching for a specific element like so:<div><div style="margin:0px;font-size:11px;font-family:Menlo;min-height:13px"><div style="margin:0px;min-height:13px"><br></div><div style="margin:0px;color:rgb(112,61,170)"><span style="color:#000000"> </span><span style="color:#bb2ca2">let</span><span style="color:#000000"> isOrderedBefore:(</span>Generator<span style="color:#000000">.</span>Element<span style="color:#000000">, </span>Generator<span style="color:#000000">.</span>Element<span style="color:#000000">) -> </span>Bool</div></div><div style="margin:0px;font-size:11px;font-family:Menlo"> <span style="color:#bb2ca2">func</span> indexOf(theElement:<span style="color:rgb(112,61,170)">Equatable</span>) -> <span style="color:rgb(112,61,170)">Index</span>? {</div><div style="margin:0px;font-size:11px;font-family:Menlo"> <span style="color:#bb2ca2">let</span> theNearestIndex = <span style="color:#bb2ca2">self</span>.binarySearch(){ <span style="color:#bb2ca2">self</span>.isOrderedBefore($0, theElement) }</div><div style="margin:0px;font-size:11px;font-family:Menlo"> <span style="color:#bb2ca2">if</span> theNearestIndex < <span style="color:#bb2ca2">self</span>.endIndex && <span style="color:#bb2ca2">self</span>[theNearestIndex] == theElement { <span style="color:#bb2ca2">return</span> theNearestIndex }</div><div style="margin:0px;font-size:11px;font-family:Menlo"> <span style="color:#bb2ca2">return</span> <span style="color:#bb2ca2">nil</span></div><div style="margin:0px;font-size:11px;font-family:Menlo"> }</div></div><div><br></div><div>I can also do things like a generic insert() method like so:</div><div><br></div><div><div style="margin:0px;font-size:11px;font-family:Menlo"> <span style="color:rgb(187,44,162)">func</span> insert(theElement:<span style="color:rgb(112,61,170)">Comparable</span>) { <span style="color:rgb(187,44,162)">self</span>.insert(theElement, atIndex: <span style="color:rgb(187,44,162)">self</span>.binarySearch(){ <span style="color:rgb(187,44,162)">self</span>.isOrderedBefore($0, theElement) }) }</div></div><div><br></div><div>(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><br></div><div>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><br></div><div>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><br></div><div>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>plus</b> a check at the end, so there might still be an argument for two methods, e.g nearestLowerBound() and nearestUpperBound().</div><div><br></div><div><br></div><div>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><br><div><blockquote type="cite"><div>On 15 Mar 2016, at 14:28, Lorenzo Racca via swift-evolution <<a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a>> wrote:</div><br><div><div style="word-wrap:break-word">Hi all, <div><br></div><div>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>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>I worked out some code, recalling the C++ functions binary_search, lower_bound and upper_bound. </div><div>I’ve tested them and they seem all right. </div><div><br></div><div>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>The code for binarySearch is : </div><div><span style="font-family:Menlo;font-size:11px;color:rgb(187,44,162)"><br></span></div><div><span style="font-family:Menlo;font-size:11px;color:rgb(187,44,162)">extension</span><span style="font-family:Menlo;font-size:11px"> </span><span style="font-family:Menlo;font-size:11px;color:rgb(112,61,170)">CollectionType</span><span style="font-family:Menlo;font-size:11px"> </span><span style="font-family:Menlo;font-size:11px;color:rgb(187,44,162)">where</span><span style="font-family:Menlo;font-size:11px"> Generator.Element : Comparable {</span></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(0,132,0)"><span> </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)"><span> </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)"><span> </span>@warn_unused_result</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">public</span> <span style="color:#bb2ca2">func</span> binarySearch(element: <span style="color:#703daa">Generator</span>.<span style="color:#703daa">Element</span>) -> <span style="color:#703daa">Index</span>? {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <br></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">var</span> left = <span style="color:#703daa">startIndex</span></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">var</span> right = <span style="color:#703daa">endIndex</span></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <br></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">while</span> (left != right) {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">let</span> mid = left.<span style="color:#3d1d81">advancedBy</span>(left.<span style="color:#3d1d81">distanceTo</span>(right) <span style="color:#3d1d81">/</span> <span style="color:#272ad8">2</span>)</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">let</span> value = <span style="color:#bb2ca2">self</span>[mid]</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <br></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">if</span> (value <span style="color:#3d1d81">==</span> element) {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">return</span> mid</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">if</span> (value <span style="color:#3d1d81"><</span> element) {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> left = mid.<span style="color:#3d1d81">advancedBy</span>(<span style="color:#272ad8">1</span>)</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">if</span> (value <span style="color:#3d1d81">></span> element) {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> right = mid</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">return</span> <span style="color:#bb2ca2">nil</span></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo">}</div><div><br></div><div>lowerBound and upperBound:</div><div><br></div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="color:#bb2ca2">extension</span> <span style="color:#703daa">CollectionType</span> <span style="color:#bb2ca2">where</span> Generator.Element : Comparable {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(0,132,0)"><span> </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)"><span> </span>/// If none, returns -1.</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(187,44,162)"><span> </span>@warn_unused_result</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">func</span> lowerBound(predicate: <span style="color:#703daa">Generator</span>.<span style="color:#703daa">Element</span> -> <span style="color:#703daa">Bool</span>) -> <span style="color:#703daa">Index</span> {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">var</span> result = <span style="color:#bb2ca2">self</span>.<span style="color:#703daa">startIndex</span>.<span style="color:#3d1d81">advancedBy</span>(-<span style="color:#272ad8">1</span>)</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">var</span> low = <span style="color:#bb2ca2">self</span>.<span style="color:#703daa">startIndex</span></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">var</span> hi = <span style="color:#bb2ca2">self</span>.<span style="color:#703daa">endIndex</span></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <br></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">while</span> low != hi {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">let</span> mid = low.<span style="color:#3d1d81">advancedBy</span>(low.<span style="color:#3d1d81">distanceTo</span>(hi) <span style="color:#3d1d81">/</span> <span style="color:#272ad8">2</span>)</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <br></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">if</span> predicate(<span style="color:#bb2ca2">self</span>[mid]) {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> result = mid</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> hi = mid</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> } <span style="color:#bb2ca2">else</span> {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> low = mid.<span style="color:#3d1d81">advancedBy</span>(<span style="color:#272ad8">1</span>)</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">return</span> result</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo">}</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"><br></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="color:#bb2ca2">extension</span> <span style="color:#703daa">CollectionType</span> <span style="color:#bb2ca2">where</span> Generator.Element : Comparable {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;color:rgb(0,132,0)"><span> </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)"><span> </span>/// If none, returns -1.</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">func</span> upperBound(predicate: <span style="color:#703daa">Generator</span>.<span style="color:#703daa">Element</span> -> <span style="color:#703daa">Bool</span>) -> <span style="color:#703daa">Index</span> {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">var</span> result = <span style="color:#703daa">startIndex</span>.<span style="color:#3d1d81">advancedBy</span>(-<span style="color:#272ad8">1</span>)</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">var</span> low = <span style="color:#703daa">startIndex</span></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">var</span> hi = <span style="color:#703daa">endIndex</span></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <br></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">while</span> low != hi {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">let</span> mid = low.<span style="color:#3d1d81">advancedBy</span>(low.<span style="color:#3d1d81">distanceTo</span>(hi) <span style="color:#3d1d81">/</span> <span style="color:#272ad8">2</span>)</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"> <br></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">if</span> predicate(<span style="color:#bb2ca2">self</span>[mid]) {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> result = mid</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> low = mid.<span style="color:#3d1d81">advancedBy</span>(<span style="color:#272ad8">1</span>)</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> } <span style="color:#bb2ca2">else</span> {</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> hi = mid</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> <span style="color:#bb2ca2">return</span> result</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"> }</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo">}</div></div><div><br></div><div>If you wish to try them, usage is :</div><div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><span style="color:#bb2ca2">var</span> array : <span style="color:#703daa">Array</span> = [<span style="color:#272ad8">1</span>,<span style="color:#272ad8">2</span>,<span style="color:#272ad8">3</span>,<span style="color:#272ad8">4</span>,<span style="color:#272ad8">5</span>]</div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo;min-height:13px"><br></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><div style="margin:0px;line-height:normal;color:rgb(0,132,0)"><span style="color:#bb2ca2">let</span><span> a = </span><span style="color:#4f8187">array</span><span>.</span><span style="color:#31595d">upperBound</span><span>{$0 < </span><span style="color:#272ad8">3</span><span>} </span>//array[a] = 2</div><div style="margin:0px;line-height:normal"><span style="color:#bb2ca2">let</span> b = <span style="color:#4f8187">array</span>.<span style="color:#31595d">lowerBound</span>{$0 > <span style="color:#272ad8">3</span>} <span style="color:#008400">//array[b] = 4</span></div></div></div><div style="margin:0px;font-size:11px;line-height:normal;font-family:Menlo"><br></div><div>What do you think? Should I commit a new file to proposals?</div><div>Should they be added to CollectionType or SequenceType?</div><div>It’s obviously open to discussion and change.</div><div><br></div><div>Thank you. </div><div><br></div><div>Best, </div><div><br></div><div><div>
Lorenzo Racca<br><a href="tel:%2B39%20345%209294756" value="+393459294756" target="_blank">+39 345 9294756</a><br><a href="mailto:lorenzo.racca@live.it" target="_blank">lorenzo.racca@live.it</a><br><br>
</div>
<br></div></div>_______________________________________________<br>swift-evolution mailing list<br><a href="mailto:swift-evolution@swift.org" target="_blank">swift-evolution@swift.org</a><br><a href="https://lists.swift.org/mailman/listinfo/swift-evolution" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br></div></blockquote></div><br></div></div><br>_______________________________________________<br>
swift-evolution mailing list<br>
<a href="mailto:swift-evolution@swift.org">swift-evolution@swift.org</a><br>
<a href="https://lists.swift.org/mailman/listinfo/swift-evolution" rel="noreferrer" target="_blank">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br>
<br></blockquote></div><br></div>