<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="">I’m kinda new to this, so here’s my idea.</div><div class="">The other day I was building an app and had to search through a pretty big array (some 100M entries), and noticed the library function “array.contains” slowed everything down a lot. So i searched on GitHub the code and found out that "SequenceType.contains” uses Linear Search. I know that Binary Search works way better with sorted arrays (which was my situation) so here it is, why not add it to the std lib? </div><div class="">I noticed it because I moved from C# where such a function is present. And I believe there is one in Java too.</div><div class=""><br class=""></div><div class="">I was working and I already figured out an algorithm that could really be just pasted into SequenceType.swift and make it easy for everyone. I even started benchmarking it and really, it would make a big difference. This is my code as of now:</div><div class=""><br class=""></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 `true` 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>/// Collection must be sorted.</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="">Bool</span> {</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo; color: rgb(61, 29, 129);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">if</span><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=""> result = </span>_customContainsEquatableElement<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class="">(element) {</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="">return</span> result</div><div style="margin: 0px; font-size: 11px; line-height: normal; font-family: Menlo;" class=""> }</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><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="">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> <span style="font-variant-ligatures: no-common-ligatures; color: #bb2ca2" class="">true</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=""> 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; color: rgb(187, 44, 162);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span>return<span style="font-variant-ligatures: no-common-ligatures; color: #000000" class=""> </span>false</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="">Now I don’t know whether this would be accepted, useful or just even right. I don’t have the permission to pull commits to the rep, so I don’t even really know how to make it an official proposal. </div><div class=""><br class=""></div><div class="">Any thoughts on this?</div><div class=""><br 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>