<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="">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="font-variant-ligatures: no-common-ligatures; color: #000000" 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="font-variant-ligatures: no-common-ligatures; color: #000000" 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="font-variant-ligatures: no-common-ligatures; color: #000000" 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><p style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></p><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><p style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></p><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><p style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></p><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="font-variant-ligatures: no-common-ligatures; color: #000000" 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="font-variant-ligatures: no-common-ligatures; color: #000000" 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="font-variant-ligatures: no-common-ligatures; color: #000000" 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><p style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></p><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><p style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></p><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="font-variant-ligatures: no-common-ligatures; color: #000000" 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="font-variant-ligatures: no-common-ligatures; color: #000000" 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><p style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></p><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><p style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; min-height: 13px;" class=""> <br class="webkit-block-placeholder"></p><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="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> a = </span><span style="font-variant-ligatures: no-common-ligatures; color: #4f8187" class="">array</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">.</span><span style="font-variant-ligatures: no-common-ligatures; color: #31595d" class="">upperBound</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">{$0 < </span><span style="font-variant-ligatures: no-common-ligatures; color: #272ad8" class="">3</span><span style="font-variant-ligatures: no-common-ligatures; color: #000000" 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></body></html>