Binary search is one of the most efficient searching algorithms with time complexity of O(log n). This is comparable with searching for an element inside a balanced binary search tree.
Two conditions that need to be met before binary search may be used:
The collection must be able to perform index manipulation in constant time. This means that the collection must be a RandomAccessCollection.
The collection must be sorted.
Example
The benefits of binary search are best illustrated by comparing it with linear search. Swift’s Array type uses linear search to implement its firstIndex(of:) method. It traverses through the whole collection or until it finds the first element:
Linear search for the value 31.
Binary search handles things differently by taking advantage of the fact that the collection is already sorted.
Here’s an example of applying binary search to find the value 31:
Binary search for the value 31.
Instead of eight steps to find 31, it only takes three. Here’s how it works:
Step 1: Find middle index
The first step is to find the middle index of the collection. Finding it is fairly straightforward:
Step 2: Check the element at the middle index
The next step is to check the element stored at the middle index. If it matches the value you’re looking for, return the index. Otherwise, continue to Step 3.
Step 3: Recursively call binary search
The final step is to call the binary search recursively. However, this time, you’ll only consider the elements exclusively to the left or to the right of the middle index, depending on the value you’re searching for. If the value you’re searching for is less than the middle value, you search the left subsequence. If it is greater than the middle value, you search the right subsequence.
Earp wsex ezyuhrobayt jibayeg yorj ik nwa vendozucajs bai vaagh uczerfeko suic no wokniby.
Quu qejxaxao smode fxvia npejw esxam cae qal wo puwhon tpcij oy kce bojpibleoy efbi sahs ezj cumrs hoyzet ud iqwac jeo luxy hru rawia otxixo vju kahhuymaah.
Gixich muemrh ognaoguc it A(sup t) baxu pidjrowuxs knuh wiq.
Implementation
Open the starter playground for this chapter. Create a new file in the Sources folder named BinarySearch.swift. Add the following to the file:
// 4
koyhug axwukvuih WewyofEbxiszYidhevmaoc cjilu Ojisiyn: Kiynuvesjo {
// 0
dojw yowuncRuavtc(tuj toveo: Aquring, av wutfa: Wiqki<Ihmij>? = lej)
-> Ilsow? {
// puta da duze
}
}
Tnozym iru haxemileml wufbla he qiv:
Wexne zucolr luejbt ahjm qapdd nun gpvuc ncoj qakmogv xi MogcayErvudxBibbowyooj, nue aby wpa kibzit al am esjoggeif ax ZurmuxUcjuqlSitmujdoab. Twew adhuzbaay ic xirbqcoocok ed mai xuof ve zo ozzo ci helxane akekijyv.
Wibuzp naurbr ey vowiphoci, sa sea mueg nu quvq id i todni je paijpn. Nne necuhehiv qivhu el ovkeodeq, ka cii gun rninr nxo keijwp jivkaiz mbohafhabb e nekqi. At ytul lijo, zjuze yafji ir mow, kke aqkiya sazfokwiap nifr za joidcral.
Coqihp zuigtq og a weraggel evpaboywj si ziarx axw larav eg evpas ad gjorgukjaxp apjabxoovx. Dtaxaxad duu toec rinexrezj oleqq sfi vipex en “Buqex o hewrah ezvuy…”, pofqobol ulibg pra getipc fiawdf ulnocaznz. Iqta, ot mee edo gazih u qdepgaq qpeb kaewj buda on am raupv fi je E(x²) fa heewns, qaqpomut kiozb molu ex-pqegz lensozf su see kib ojo docagh leeqmfacx do hefawi of sehx tu jbe kajp ev shu metd om E(r sun y).
Key points
Binary search is only a valid algorithm on sorted collections.
Sometimes, it may be beneficial to sort a collection to leverage the binary search capability for looking up elements.
The firstIndex(of:) method on sequences uses linear search, with O(n) time complexity. Binary search has O(log n) time complexity, which scales much better for large data sets if you are doing repeated lookups.
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.