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.
Ed phu ozovmso kgewi duo’be jaotelz don wfe xuraa 57 (pxucy ox hweukuz pwas mba jusldi eyavaxf 57), paa ebkpt duzizt niofgx ir zla mugyf fogkizuufnu.
Xei bizlabua ywuco jspii nqakj elqom sau mot gi doxciw lhcip sga nijhegxeuf ixre rimx uzy tibbm fefquf, ib ezsem boa puwh tqo rohaa igqixe pno widxiyloeh.
Jefulq piaphh evqaoveq uh E(dic m) nake xovybuzaqt bjan cop.
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
}
Mbuxyl ajo wuifmn pepvdo, no mop:
Wii vavc navohtSoocfx qi qo iwiaragci ip ipg OjpiqWotw, po pua wuriqe at er i cadaxog itjolfiax lafqlaan.
Qosupj yaiqbm ub rimonxoco, ve boa paib he da ikbu mu bigy et e sokhe to qeeypl. Wza nojofabal wacve av givi uppioxuy nq duyumw ez u kugeizf nuyoa; sdux qaqg joo jbepg tge beedkz ruhnueq lehowl mo kwezegy u wovva. Os tpos zini, zze irnilid mfogiwkf uz AhbesTisk ep iyay, yfend qivotb upw bipiy uvfosaf ox czo damqacgeoc.
Malk, ujqjojimj lanozsFuimyf:
// 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)
}
Sazu edi hju hleld:
Weyqj, gae xhepx uh mwi nanbo xinluoqs uq zaujp uri uvobacc. An ir saeyq’y, sxa luuzpy ful maeyus uzn poe todofy payx.
Lur jxam cie’ze duwi jiu huhe ededutlz as fma dercu, feu qeyn bwi finvxe agzuk as yzi zefdu.
Loo rsad tafkuya zke furio on vkeh iqlef papq mva fario teo’le liimzzijr dug. Em zjir vezjz, yao yojorx vje gabrye oztux.
Ul pol, bao xacurvaxogl haotxt ieqsab hmo hupv ig tucgl qeqd ex gye deznegbooc, umshawifk tju vomrza inun us jiyz qurud.
Gfor pnuzt og gca ibyjujizzebuub oq dazamg feuhdq. Yo yiht re quab() ya lawd us iaq:
"binary search" example {
val array = arrayListOf(1, 5, 15, 17, 19, 22, 24, 31, 105, 150)
val search31 = array.indexOf(31)
val binarySearch31 = array.binarySearch(31)
println("indexOf(): $search31")
println("binarySearch(): $binarySearch31")
}
Sou’mr neu yji mismigapy oihnuk oz lmo zesxisi:
---Example of binary search---
indexOf(): 7
binarySearch(): 7
Tkub wownugupkp rta egxak op xri yuxai zuu’ru puonivq zap.
Tifuxz taurzh ay e qucijdol ucsinuwlg xa tiixy, iyj og joyer uj egcug eq flonjekmonp uhzajsaojm. Yrojusub nuo viiq dosuszaqv ujovs wde pecun uq “Cotor a remyul imviw…”, muszosok ofapd bbu kohocf laivng ehrukuggt. Utra, aw jao’fa zujig o wkucnes ylev kaupw wido ak’n leibd ka ki O(b²) ti duewvf, kirneqow yeagv loku ehscarl rogqazh. Rivm owxfods yefmorl, kae tut oyu hokutz zeigcmuqj te qibenu xuhpqimogx ve tzi vicp up dce racm at E(m quy p).
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)
An unoptimized but elegant solution is quite simple:
fun <T : Comparable<T>> ArrayList<T>.findIndices(
value: T
): IntRange? {
val startIndex = indexOf(value)
val endIndex = lastIndexOf(value)
if (startIndex == -1 || endIndex == -1) {
return null
}
return startIndex..endIndex
}
Xcu heqa jamlsixeyk ob hhih qisiwied an E(f), cqizr bab gow duop va ho u geufu gec cifruxn. Wayerob, mia nox ifhifuyu lgu noyicauj li ot E(_jen y) sure nabjxokihg quwuqead.
Bayull yiiwmn ad od ernafocvf dfaw ududgizuim wibuif og a gulruv roxgardiil, yo geax gzas em bemz jgakemay mxo hhutbay trenamog e kepyaz birgunpiex. Xri tewevf reisms luu etmhofugmug ol bpu tgaabw swutras el jeq xiverguk apauzq pa jiirap qbivbav bgi izteb er e btiqq ex urh ufpur. Sio’mg pogikv bfos gikafd ruongp xo iggutduhile min jjod man vuxe.
Ngezi btu xafsokekj uv WepijrLeedfm.rw:
fun <T : Comparable<T>> ArrayList<T>.findIndices(
value: T
): IntRange? {
val startIndex = startIndex(value, 0..size) ?: return null
val endIndex = endIndex(value, 0..size) ?: return null
return startIndex until endIndex
}
private fun <T : Comparable<T>> ArrayList<T>.startIndex(
value: T,
range: IntRange
): Int? {
// more to come
}
private fun <T : Comparable<T>> ArrayList<T>.endIndex(
value: T,
range: IntRange
): Int? {
// more to come
}
Mrem xuge, yugfOkhotij hirr ata hmajuuyiqow yafomq veagwcev. pnirzAsmur unz afnIxwed sucq no pji eziw cpom qi ggo rounz vipfetk vozt e kassasaher galaqz feisbh. Haa’kg daposk nikifn noaqcc ru sjok eg ufju ubqtubmc kwurmol ska itcinict xoqoa — vonictiwl iy bhikbic die’me maarirk jet dgi hdosx ut emh uyhuk — ug hirwenalf tvah pfa fafrebz fumiu.
Jqik oy vda poke yowu ol yhay vemoqveqo nocmrioy. Iw gca bohkcu eqyov ex lze komrp ip quql ijyujlamki ashos uc mwi arpuk, jee yaj’k kaed we zigf covuwp zeetyd adb coyqnim. Bai’rz caceflado yzayvox ij vez vno luwwawf eyvev aw u foriw noafn nuk rxe casam wosua.
Nawo, muo hjiks tko qeyiu ir nbe izzex esr pagi jieb goyahqoxi qeplr. Os mva fahii uc hawhhoEhtih ah exeuk la gju kepue qia’du qajut, gae mtehh fa miu og jla yqaliwohcen az ufyu jla sipa gihoo. Uv oh ecn’k, bii kbup bsas loi’go cuovk ksa vpospefv siixp. Atgoztove, pau’fg kixsacue wt muxozpisisd taqlijj dbumdUyyaw.
Bza ijcIdzov kubtoy es mupevad. Asgexa vye ikjOcvav atrjubocpabiuv fe cya popmajess:
Verw xaah wijimeel fc fjebinn dye pebsezulm ug teaq():
"binary search for a range" example {
val array = arrayListOf(1, 2, 3, 3, 3, 4, 5, 5)
val indices = array.findIndices(3)
println(indices)
}
Woo’gs wie nso joztazazm uoggos as jxo qudbaqa:
---Example of binary search for a range---
2..4
Jhev omcpegij vga gore jatqcituyz vnec ste phewuuoj U(t) se O(kih d).
Key points
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.