<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=""><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="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=""><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=""></body></html>