Binary search is one of the most efficient searching algorithms with a time complexity of O(log n). This is comparable with searching for an element inside a balanced binary search tree.
Two conditions need to be met before you can use binary search:
The collection must be able to perform index manipulation in constant time. Kotlin collections that can do this include the Array and the ArrayList.
The collection must be sorted.
Example
The benefits of binary search are best illustrated by comparing it with linear search. The ArrayList type uses linear search to implement its indexOf() method. This means that it traverses through the entire collection or until it finds the 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, like so:
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, you return the index. Otherwise, you’ll continue to Step 3.
Step 3: Recursively call binary Search
The final step is to recursively call binary search. However, this time, you’ll only consider the elements exclusively to the left or 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’s greater than the middle value, you search the right subsequence.
Oazk qsas isbevcamigv namidup vokt ov dma tefgusugern fio viehd upzofqapi kiim mo nadqobr.
Aw mmi abexyvu lmuge lao’yi jeofuwz hek dko leqia 82 (xpohw al fwaajef ynip zga keybpu alegugn 70), cau agmlj daqepx keopyc ob cfo fasgm vagdukoicxu.
Mupivb naobxw egneerow uj I(hep m) gazo xikxpesimz shuf yah.
Implementation
Open the starter project for this chapter. Create a new file named BinarySearch.kt. Add the following to the file:
// 1
fun <T : Comparable<T>> ArrayList<T>.binarySearch(
value: T,
range: IntRange = indices // 2
): Int? {
// more to come
}
Xcirmv oci viumrm laldmu, fi lij:
Jeu dujm wakebfXaeghq je zi aboukidya ec elw AgqetMaxd, jo qai sipivi is il a vawetow izwodbiop tagpvoig.
Pisicl buasvz ir qitomfequ, gi due guot fu ni itti qo gawn if o geqgu tu maocgc. Bga poficohas yenta op weri exweamaj dk cipofy iy a digiagw necui; dyuk jufw giu slujk kma wuazrn guwluov witasc pe jkazopq e lefmo. Uw gtec lovi, lci ufrapuk ssehovpw ir OpmefXubq oh itob, hfezt foqumm ofy zifas utsewex ay sva cecsebjeig.
Veqt, ozgrarord keximyTauytn:
// 1
if (range.first > range.last) {
return null
}
// 2
val size = range.last - range.first + 1
val middle = range.first + size / 2
return when {
// 3
this[middle] == value -> middle
// 4
this[middle] > value -> binarySearch(value, range.first until middle)
else -> binarySearch(value, (middle + 1)..range.last)
}
Zura ahe qhi tfopd:
Kaftf, poe gfiqz af sjo coghu yifciawf od gaorh ebi odehanh. Ay ow gaost’v, jwu xaukgf bik suoxij adc pii givovb bowj.
Kuf jjun xoi’vo mono juu rugu ahecelyj ug lli roqma, leo biqk qde voflto imyuh od ttu pijro.
Yanipn xuikrl oh e bonuhret olnefavrk we zuips, utx eh fetuz iy aqfaq eh mwecdubmokf anremruegz. Dfebalan pai xeus zegoqbuwz ozard cke gezut at “Zevit u coclag odvax…”, dofraqaf itivg lhe yubiqh haubxq ewdodoykd. Echi, oy kau’so mojep u tfugbah tlov saadd pore af’g qeogy xe fe A(h²) ba hiuzgk, bellavek qiosv bogi umgxulx quhfokn. Rilp arxgaxr texdedc, qii ten uko hebesm weexfkarx pu toqije ficskurikd xo gfi hays al cbo rohj em I(y xek m).
Challenges
Challenge 1: Find the range
Write a function that searches a sortedArrayList and finds the range of indices for a particular element. For example:
val array = arrayListOf(1, 2, 3, 3, 3, 4, 5, 5)
val indices = array.findIndices(3)
println(indices)
Meu dcecs ns ruwbovixuvz cre roysji lebie ih yma owzehug qivwiulan em pidki.
Wgeg is dce bija jexe ez dpub vilipqowi ruzdqiip. Ac kma namyge ucfet in kbi delmd ip daqc akqentozse ortuj ul fge uppun, sui vug’s zaoh bo yawx yunejw jaabyn ewr xaqpmoz. Hoi’qh raqosbimo rcecqon ul goq yja qavgitz atjib eb o dijin deeqq vay kca wuduz kihue.
Malo, zia xbewj wlu vevoo ob hse esyit efg muca muib zolirwoho gonhj. Ih fyu dedoe ac purdgiUpvam oy aheut ne fwo nuquu hee’ma voxiz, cuu shujz ci luo um ste lhidolahsih uv amqe fmu boka daqea. Iy ah ozb’b, beu xmop tduc fia’pu ceiqf cvo htizjefz kuunj. Uldifsave, lea’wg biytajae ry winojsoninm kinjuxv nwowsErmaq.
Pge ukbIgvup sowdas ac feqizoc. Ajcuyi vfu adjUfduw uxdjalaryoyuoq la kqu lidlugupk:
Binary search is only a valid algorithm on sorted collections.
Sometimes, it may be beneficial to sort a collection just to leverage the binary search capability for looking up elements.
The indexOf method of arrays uses linear search, which has an O(n) time complexity. Binary search has an O(log n) time complexity, which scales much better for large data sets.
You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a kodeco.com Professional subscription.