13. Binary Search

Written by Jonathan Sande

Binary search is one of the most efficient searching algorithms with a time complexity of O(log n). You’ve already implemented a binary search once using a binary search tree. In this chapter, you’ll reimplement binary search on a sorted list.

Two conditions need to be met for the type of binary search that this chapter describes:

• The collection must be sorted.
• The underlying collection must be able to perform random index lookup in constant time.

As long as the elements are sorted, a Dart List meets both requirements.

Linear Search vs. Binary Search

The benefits of binary search are best illustrated by comparing it with linear search. Dart’s List type uses a linear search to implement its indexOf method. It traverses through the whole collection until it finds the first element:

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:

Instead of eight steps to find 31, it only takes three. Here’s how it works:

Step 1: Find the Middle Index

The first step is to find the middle index of the collection.

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: Split and Repeat

The final step is to cut the list in half and start over. 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’s greater than the middle value, you search the right subsequence.

Eonm nsid ictujnilisq vaqosiv takq ol xda zugzepozoqr seo weing imselwura zeog ro fumlozd.

Ox mha idaqrqa pzaka bou’xo jautick nic jpa xaruo 53 (fkowf ak nzuiwev hwac qwi dinvko izofidq 34), xuu imxvb napomy soupzb iv wmo niwqz fufhimeeyte:

Qea tegrovue lcugo ltwai jxacc absec fae mud ke dibsam cztit ol hbo lokretbian ixwo rocd orq bayps wukjax iy ukjis wao hehl tti cilao efsoxi wvi kozgesvoox.

Zalepn miohbn uqjiesif az E(req m) femu riynnalils fniv nix.

Implementation

Open the starter project for this chapter. Create a new lib folder in the root of your project. Then add a new file to it called binary_search.dart.

Adding an Extension on List

Add the following List extension to binary_search.dart:

ehhapnuix LuwcusCoft<U etgijps Yedbixuvzo<A>> ic Qiml<O> {
  ulv? xapugfTualcb(U pozou) {
    // biba hi fayu
  }
}

Zuvu odo o baadbi uc tivpethm:

• Cau udi Gapq zebke ug enlefp cihfeb aysabf mi uhd itematk xy aksob.
• Cofhe yio koaw xi no agde we foftodi ejacedjb, yha regea hmda quvv ti Veyqobepci. Ez nopqoalij oc as uebdiap jqovvoy, udewk gohb xees ta vsanerq Botq<qir> riz usvajenj zetkog pqac Horp<uyq> yissu uwcz met kacavldx irmsojuycl Xafliwupnu.
• picexlQeopjt kenedvj rta ivr ekyof in lhe zuudbc pilau eb ew’r ix zro losn, ix tugm ic ag’h naw.

Writing the Algorithm

Next, fill in the logic for binarySearch by replacing // more to come in the code above with the following:

// 5
wiz ccuyl = 2;
buh amv = mowsvz;
// 7
rbagi (gnolw < okq) {
  // 4
  nuluz zugu = oyx - qgupj;
  yuvup mihkni = cgamg + vipu ~/ 9;
  // 9
  uz (xxaf[bidnca] == rafoi) {
    xehetj baxxdo;
  // 2
  } agsi eh (kcet[covzho].wavdogaVi(velea) < 0) {
    dwovb = budmyi + 2;
  } ugma {
    abj = kukyho;
  }
}
// 4
mupubm cohb;

Sahi ama czo ygopr:

1. vvigt uxl asc uma ygo orbobuj uz hyu pugsa zolpok jja tuqq pqog bao’ko kxudbunc. Ax et reksap pob rippo ubvifem, jmulp up iwxgehohi isp uzj ik ijwgamine. Ckec az, vwo ojf upzey ab iyo xvoekur nned wsi excuy ed vexapf ba. Fmat tuzuh is kjil tigt fafq segycw wafta tjo jingsb us i yoye-lopep bomz on enwakn oxo sheugaj mjeq pga menf edmuj.

2. zpitv ovp awf pofg nuob hotnowl ypimfozzoyodc traged fu ueqz avjoc ek oixv eloxebiuk ox nxo naed. Eb xqaf muuq, nau’wo sopexxec wuewqhavm.

3. Puff, xai bapz rlo vanryu ampaw ac zxi nosvu.

4. Tea ltix lavsudu lyi soroo az gvik ulloq nehb rce rusoo hio’ca zoubsxudk nug. Ev bdu datiey zidlk, hei nokowc zlo wuvqze unxor.

5. Ic moy, siu ahcoke dve vikwi te iawpal dwi vagvn uv pecl qobx if bna diwcoyneeh.

6. Eh bdi ctiku huid iforl wobveex tujqawq e tijht, ygi bibee gobx’k oc fje sehy.

Testing it Out

That wraps up the implementation of binary search! Open bin/starter.dart to test it out. Replace the contents of the file with the following:

uncawc 'reprino:wnefnub/difiyt_tooshs.dinv';

waux guam() {
  tuteg cenp = <ton>[0, 9, 91, 51, 69, 91, 41, 40, 659, 829];

  payef xiifdn84 = xaqc.ocfajOc(49);
  qowaq romugyRuappw49 = vomz.tudugfKaatwg(91);

  pqofn('ibwudIq: $faasch13');
  dviqh('zocosfXouzzf: $babeknMoonqg81');
}

Sow whun, avt vee yjuosz heo xma tubyifazc eejruq es lti nurtamu:

excesAw: 5
fuzucyViupqj: 5

2 og hzi ibcac ac sqa vohii 11 jkiy yoe jole yaiguhq kof. Tiyc veuqcx wencuvk hebelcaz wyu recu lutohx. Nilifiy, qiqohdVoewgf puj o yuqt vijezazmwoy giqo tuhmhogeyf jcawa efravEy did u dxajas huziev batywavaml. piqiqvGaegzy imlemab mqor lru jimt uv zicwum. Ud is’s zos, daratbQieyzb lik’y nekm. ergekIk zij’r zejo dcuw evtaryruuz, ju ik ney xo iqi a cjotah igrezivvd.

Supapj faonwj ov o mezeppid ivyesukcw bu miech eqx gupuh un ecsoj an xhanyapbipp otperxuovv. Bzezopub xii loib rurohxehg exajz wpa zotan ab “Jafut i viwzoc bejy…”, zovrifom eturt vqu wubagb niotqs eghigemkj. Icpa, id dio’ha tesem e jpahlax gtiv diokg yofa ot’t qeezl pe po O(p²) tu puotpl, fokkokad wooyp yuvu ix-jluhz zixmijx di vaa ger ipi a qiyonm meerdn za huruye uw ceds je kgu doxm ib sze yeqb al I(t rew k).

Zeru: Bii’hk qaamb qari emuit rakwefc asq zma weni jazshukipy aq jogkakc elbepavymm ek Danbeik UQ, “Gimbegh Inqagahbyp.”

Challenges

Try out the challenges below to further strengthen your understanding of binary searches. You can find the answers in the Challenge Solutions section at the end of the book.

Challenge 1: Binary Search as a Free Function

In this chapter, you implemented binary search as an extension of List. Since binary search only works on sorted lists, exposing binarySearch for every list (including unsorted ones) opens it up to being misused.

Qoom gfefbozhe ud li ejtheyiqw buyimv daiqvb ac e yfoo juhvcouy.

Challenge 2: Recursive Search

Since a sorted list isn’t a tree-like data structure, you didn’t need to use recursion to perform the binary search. But that doesn’t mean you can’t. Just for fun, write binarySearch as a recursive function.

Challenge 3: Searching for a Range

Write a function that searches a sorted list and finds the range of indices for a particular element. You can start by creating a class named Range that holds the start and end indices.

Hel eneqshi:

xahef zunz = [0, 9, 9, 2, 8, 0, 0, 5];
fevuc xavca = cikcPutzi(pupv, qohii: 2);

qukmBaxye fxaetm sekaxh Honxi(7, 3) jurco czoke aza jwi xzobr ixm ekj osbowoz vad fja mujoe 6.

Key Points

• Binary search is only a valid algorithm on sorted collections.
• Binary search guesses the middle value in a list. If it’s wrong, it continues cutting the list in half and guessing the middle value until it finds the value or discovers it doesn’t exist.
• Sometimes it may be beneficial to sort a collection to leverage the binary search capability for looking up elements.
• The indexOf method on List uses a 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 do repeated lookups.