<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="">In my mind, caller should be guarantee that array is sorted. As an example, in Objective-C SDK, NSArray should be is sorted before for using binary search method.<div class="">But this is a good idea to make a SortedArray. <br class=""><div class="">
<div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="color: rgb(0, 0, 0); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><p dir="ltr" style="color: rgb(96, 96, 96); font-size: 15px; line-height: 22.5px; margin: 1em 0px; padding: 0px;" class="">Best regards, Igor Vasilenko <br class=""></p><p dir="ltr" style="color: rgb(96, 96, 96); font-size: 15px; line-height: 22.5px; margin: 1em 0px; padding: 0px;" class="">iOS Developer at Yota</p><p dir="ltr" style="color: rgb(96, 96, 96); font-size: 15px; line-height: 22.5px; margin: 1em 0px; padding: 0px;" class="">+7 (999) 527 - 07 - 59<br class=""><span style="line-height: 1.6em;" class=""><a href="mailto:name.surname@e-legion.com" target="_blank" class="">spb.vasilenko@gmail.com</a></span><br class=""><a href="http://www.e-legion.com/" target="_blank" style="line-height: 1.6em; word-wrap: break-word; color: rgb(109, 198, 221);" class="">www.spbvasilenko.github.io</a></p></div></div><br class="Apple-interchange-newline"></div><br class="Apple-interchange-newline"></div><br class="Apple-interchange-newline"></div><br class="Apple-interchange-newline"></div><br class="Apple-interchange-newline"></div><br class="Apple-interchange-newline"><br class="Apple-interchange-newline">
</div>
<br class=""><div><blockquote type="cite" class=""><div class="">On 07 Sep 2016, at 12:08, Charlie Monroe <<a href="mailto:charlie@charliemonroe.net" class="">charlie@charliemonroe.net</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="">Aside from this being additive (i.e. out of scope for Swift 4), this requires the array to be sorted in order for the search to work - who will guarantee this? The caller? What happens when this is called on an array that is not sorted? You likely get nil, while the item is in the array (false negative).<div class=""><br class=""></div><div class="">This would probably make sense by not extending Array itself, but introducing SortedArray which would automatically keep its members sorted instead - this way there would be a guarantee that the array is sorted and the user won't have to deal with sorting the array. It would however be at the cost of O(log N) for insertion...</div><div class=""><div class=""><br class=""><div class=""><blockquote type="cite" class=""><div class="">On Sep 7, 2016, at 10:59 AM, Igor Vasilenko 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=""><div class=""><b class="">Introduction</b></div><div class=""><br class=""></div><div class="">Right now, for Array implemented <span style="color: rgb(207, 191, 178); font-family: Menlo; font-variant-ligatures: no-common-ligatures;" class="">array.</span><span style="font-family: Menlo; font-variant-ligatures: no-common-ligatures; color: rgb(192, 191, 191);" class="">contains</span><span style="color: rgb(207, 191, 178); font-family: Menlo; font-variant-ligatures: no-common-ligatures;" class="">(element) </span>and <span style="color: rgb(207, 191, 178); font-family: Menlo; font-variant-ligatures: no-common-ligatures;" class="">array.</span><span style="font-family: Menlo; font-variant-ligatures: no-common-ligatures; color: rgb(192, 191, 191);" class="">indexOf</span><span style="color: rgb(207, 191, 178); font-family: Menlo; font-variant-ligatures: no-common-ligatures;" class="">(element)</span>for searching in an array. Both of these methods iterate over all elements in the array, starting at index 0, until they find a match. In the worst case (there is no match), they have to iterate over the entire array. In big O notation, the methods’ performance characteristic is O(n). This is usually not a problem for small arrays with only a few dozen elements. But if your code regularly needs to find objects in arrays with thousands of elements, you may want to look for a faster search algorithm.</div><div class=""><br class=""></div><div class=""><b class="">Motivation</b></div><div class=""><br class=""></div><div class="">If the array is sorted by the search key, binary search can give you a huge boost in performance. By comparing the middle element in the array to the search item, the algorithm effectively halves the number of elements it has to search trough with each iteration. Binary search has O(log n) performance. What does this mean in practice? Searching a sorted array of 100,000 elements using binary search would require at most 17 comparisons compared to the 50,000 comparisons a naive linear search would take on average.</div><div class=""><br class=""></div><div class=""><b class="">Detailed design</b></div><div class=""><br class=""></div><div class=""><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">public</span><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">func</span><span style="font-variant-ligatures: no-common-ligatures" class=""> binarySearch<T: </span><span style="font-variant-ligatures: no-common-ligatures; color: #88aab3" class="">Comparable</span><span style="font-variant-ligatures: no-common-ligatures" class="">>(array: [</span><span style="font-variant-ligatures: no-common-ligatures; color: #85b4a1" class="">T</span><span style="font-variant-ligatures: no-common-ligatures" class="">], key: </span><span style="font-variant-ligatures: no-common-ligatures; color: #85b4a1" class="">T</span><span style="font-variant-ligatures: no-common-ligatures" class="">, range: </span><span style="font-variant-ligatures: no-common-ligatures; color: #d1d4f7" class="">Range</span><span style="font-variant-ligatures: no-common-ligatures" class=""><</span><span style="font-variant-ligatures: no-common-ligatures; color: #d1d4f7" class="">Int</span><span style="font-variant-ligatures: no-common-ligatures" class="">>) -> </span><span style="font-variant-ligatures: no-common-ligatures; color: #d1d4f7" class="">Int</span><span style="font-variant-ligatures: no-common-ligatures" class="">? {</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">if</span><span style="font-variant-ligatures: no-common-ligatures" class=""> range.</span><span style="font-variant-ligatures: no-common-ligatures; color: #a589b4" class="">startIndex</span><span style="font-variant-ligatures: no-common-ligatures" class=""> >= range.</span><span style="font-variant-ligatures: no-common-ligatures; color: #a589b4" class="">endIndex</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">return</span><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">nil</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> } </span><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">else</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">let</span><span style="font-variant-ligatures: no-common-ligatures" class=""> midIndex = range.</span><span style="font-variant-ligatures: no-common-ligatures; color: #a589b4" class="">endIndex</span><span style="font-variant-ligatures: no-common-ligatures" class=""> + (range.</span><span style="font-variant-ligatures: no-common-ligatures; color: #a589b4" class="">endIndex</span><span style="font-variant-ligatures: no-common-ligatures" class=""> - range.</span><span style="font-variant-ligatures: no-common-ligatures; color: #a589b4" class="">startIndex</span><span style="font-variant-ligatures: no-common-ligatures" class="">) / </span><span style="font-variant-ligatures: no-common-ligatures; color: #7aa7c7" class="">2</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">if</span><span style="font-variant-ligatures: no-common-ligatures" class=""> array[midIndex] </span><span style="font-variant-ligatures: no-common-ligatures; color: #c0bfbf" class="">></span><span style="font-variant-ligatures: no-common-ligatures" class=""> key {</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">return</span><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #b6c1cf" class="">binarySearch</span><span style="font-variant-ligatures: no-common-ligatures" class="">(array, key: key, range: range.</span><span style="font-variant-ligatures: no-common-ligatures; color: #a589b4" class="">startIndex</span><span style="font-variant-ligatures: no-common-ligatures" class=""> ..< midIndex)</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> } </span><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">else</span><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">if</span><span style="font-variant-ligatures: no-common-ligatures" class=""> array[midIndex] </span><span style="font-variant-ligatures: no-common-ligatures; color: #c0bfbf" class=""><</span><span style="font-variant-ligatures: no-common-ligatures" class=""> key {</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">return</span><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #b6c1cf" class="">binarySearch</span><span style="font-variant-ligatures: no-common-ligatures" class="">(array, key: key, range: midIndex + </span><span style="font-variant-ligatures: no-common-ligatures; color: #7aa7c7" class="">1</span><span style="font-variant-ligatures: no-common-ligatures" class=""> ..< range.</span><span style="font-variant-ligatures: no-common-ligatures; color: #a589b4" class="">endIndex</span><span style="font-variant-ligatures: no-common-ligatures" class="">)</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> } </span><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">else</span><span style="font-variant-ligatures: no-common-ligatures" class=""> {</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> </span><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">return</span><span style="font-variant-ligatures: no-common-ligatures" class=""> midIndex</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> }</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""> }</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures" class="">}</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178); min-height: 14px;" class=""><span style="font-variant-ligatures: no-common-ligatures" class=""></span><br class=""></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #d2813d" class="">let</span><span style="font-variant-ligatures: no-common-ligatures" class=""> numbers = [</span><span style="font-variant-ligatures: no-common-ligatures; color: #7aa7c7" class="">1</span><span style="font-variant-ligatures: no-common-ligatures" class="">, </span><span style="font-variant-ligatures: no-common-ligatures; color: #7aa7c7" class="">2</span><span style="font-variant-ligatures: no-common-ligatures" class="">, </span><span style="font-variant-ligatures: no-common-ligatures; color: #7aa7c7" class="">3</span><span style="font-variant-ligatures: no-common-ligatures" class="">, </span><span style="font-variant-ligatures: no-common-ligatures; color: #7aa7c7" class="">4</span><span style="font-variant-ligatures: no-common-ligatures" class="">, </span><span style="font-variant-ligatures: no-common-ligatures; color: #7aa7c7" class="">5</span><span style="font-variant-ligatures: no-common-ligatures" class="">]</span></div><div style="margin: 0px; line-height: normal; font-family: Menlo; color: rgb(207, 191, 178);" class=""><span style="font-variant-ligatures: no-common-ligatures; color: #b6c1cf" class="">binarySearch</span><span style="font-variant-ligatures: no-common-ligatures" class="">(</span><span style="font-variant-ligatures: no-common-ligatures; color: #a589b4" class="">numbers</span><span style="font-variant-ligatures: no-common-ligatures" class="">, key: </span><span style="font-variant-ligatures: no-common-ligatures; color: #7aa7c7" class="">3</span><span style="font-variant-ligatures: no-common-ligatures" class="">, range: </span><span style="font-variant-ligatures: no-common-ligatures; color: #7aa7c7" class="">1</span><span style="font-variant-ligatures: no-common-ligatures" class=""> ..< </span><span style="font-variant-ligatures: no-common-ligatures; color: #a589b4" class="">numbers</span><span style="font-variant-ligatures: no-common-ligatures" class="">.</span><span style="font-variant-ligatures: no-common-ligatures; color: #a589b4" class="">count</span><span style="font-variant-ligatures: no-common-ligatures" class="">)</span></div></div><div class="">
<div style="letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><div style="letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px; word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><p dir="ltr" style="color: rgb(96, 96, 96); font-size: 15px; line-height: 22.5px; margin: 1em 0px; padding: 0px;" class="">Best regards, Igor Vasilenko <br class=""></p><p dir="ltr" style="color: rgb(96, 96, 96); font-size: 15px; line-height: 22.5px; margin: 1em 0px; padding: 0px;" class="">iOS Developer at Yota</p><p dir="ltr" style="color: rgb(96, 96, 96); font-size: 15px; line-height: 22.5px; margin: 1em 0px; padding: 0px;" class=""><span style="line-height: 1.6em;" class=""><a href="mailto:name.surname@e-legion.com" target="_blank" class="">spb.vasilenko@gmail.com</a></span><br class=""></p></div></div><br class="Apple-interchange-newline"></div><br class="Apple-interchange-newline"></div><br class="Apple-interchange-newline"></div><br class="Apple-interchange-newline"></div><br class="Apple-interchange-newline"></div><br class="Apple-interchange-newline"><br class="Apple-interchange-newline">
</div>
<br class=""></div>_______________________________________________<br class="">swift-evolution mailing list<br class=""><a href="mailto:swift-evolution@swift.org" class="">swift-evolution@swift.org</a><br class=""><a href="https://lists.swift.org/mailman/listinfo/swift-evolution" class="">https://lists.swift.org/mailman/listinfo/swift-evolution</a><br class=""></div></blockquote></div><br class=""></div></div></div></div></blockquote></div><br class=""></div></body></html>