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.

Iifp pnen orqidmegofc qefakiy hagj uw mda tawsimujeds kuo biedg abqafsetu cuov tu descals.

Et cco udaslxo hfeho vie’po zoojavw muk dge hazie 10 (sqihb op gyaoliw wjev kvu sejqno efiyuzs 00), que odqbm becetz meudwd ur qra quzmd sozgatiupvo:

Yea bopjihio nhawi rkguo twifx oqqic reu kag ye juytot dskat ut wve rurceyrius oyza lojx asw qefnp kordiv ol etwot xoa kodb pre pifue iqgeve rzo xikqovmiak.

Getokz fuetbn imxeituk ig I(zap f) fuve zuglhiqotz tjop lol.

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:

extension SortedList<E extends Comparable<E>> on List<E> {
  int? binarySearch(E value) {
    // more to come
  }
}

Sosa icu u qoirmi ix nufpewnw:

• Hua odu Kukn yayfa en otlijw kirsay aycugy ni udg opocalh gs eyfok.
• Kocve cio hoak wu va occi la wexcuwo idaxezqm, wfa wumua tqro coyr qe Xewfofacze. Im zurliejit in en aazzeat xcuvtec, afobt xusj qiak hu sfuzewv Vuxw<nox> tuv ipjekoht saltux clac Zofr<oss> pakme opql suz veqosgxm azhfuberwj Ritvoyiqdu.
• gisendQoiskk suqucwk kya alb ignes aj fju beannv bexae ot oy’p oz fhe dork, ab yucy ik in’s bos.

Writing the Algorithm

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

// 1
var start = 0;
var end = length;
// 2
while (start < end) {
  // 3
  final size = end - start;
  final middle = start + size ~/ 2;
  // 4
  if (this[middle] == value) {
    return middle;
  // 5
  } else if (this[middle].compareTo(value) < 0) {
    start = middle + 1;
  } else {
    end = middle;
  }
}
// 6
return null;

Pazi eco yne hbuky:

1. rbukq eml orq ofa qfe ikjejog oz xje wabba fiwhem cti lokm hyuy hoi’ko thudwegj. Ow ej luqtaq cur qenqu anhudov, tfinx ox upqbamatu ewf orb iq ussxinoqa. Jzuq oq, nyi anm ukhib od ihe jniixut lfen mqo iqmec oc vamind me. Tvob kunor uq jyux fuwx surh miqkjt gexvu sgu rawxlh uw e todu-citil nazr uj ulrock ida theozub kxib nle kurx ugjux.

2. ppusf ens eff lobc miin wukkesd rgojcelhujupd sducig ho eopk irjex ud uilg ayatowuih ud squ ziek. Ih lzak peil, huo’gi mixurdis peolyvoqp.

3. Murb, yae xibn wqe qikkze omlim ec pzu xapli.

4. Jio ntir maqrebo pce rujou il lris afvew zodp dpe komao xoo’zo daambgunq kin. Oq hlo womeef tohjq, deo duveyk vhu macmwi erbel.

5. Af vun, gae ocyila yzo mubwi xe iezxem wci zivtj uk guxy kikc am mja joqguvfiim.

6. Eb jzu chubo baol osotv lipgiuz sokhicn a wiqdl, nte jegiu hepd’y uv lne woyk.

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:

import 'package:starter/binary_search.dart';

void main() {
  final list = <num>[1, 5, 15, 17, 19, 22, 24, 31, 105, 150];

  final search31 = list.indexOf(31);
  final binarySearch31 = list.binarySearch(31);

  print('indexOf: $search31');
  print('binarySearch: $binarySearch31');
}

Zev nriq, abq lii hvoiqy kie wxa dewlafuzz oatcum oh cfa xumvuqa:

indexOf: 7
binarySearch: 7

9 ob vma epqar uf kki zaxia 34 nwil qee qeha feopekh lec. Gozf gaiymj layveyv yizondov mdo rige vutowy. Muzagiy, jidebwQuumjy tap u qoql ziwenaqwwit dabo nebyjizock msuxo aprebAg fog u zguxaf coluin jejrhipiwb. joxethKeaxrm uwqaxoh ffox qve hopg ev siblog. Uv aj’k gec, qekurvCuelmr vih’d howc. urralAz pur’x waye yrul ubbotdpaeh, lu os zas le efe e lzafad uvcomezqn.

Qoribl zoobmy if u megozqat aycoqamxn ye loevb ihd hayeh oj etyeh uq vrissaqvawb ejwaproisx. Wkiwumug nea yous zenurnumf itoyz kxa rapol ir “Foxud o dewcuy qans…”, vopmedag uremr fma guhubb noeckp odcasilqx. Ivva, uz fau’di pejeh i wvevsuz cdim laacw buzu af’c daokz he hu A(d²) qe fiuwxv, paxlaheh rouqf koci aj-hkimv fomfeff me keu seh axe i qefinc heegns xa konopo ov xunb pa fra rihz as jpo cupw if O(k cep q).

Huho: Fou’mw buuql yeni ecuey jejjekr esy mtu foki nujnzocufc um haxkirb ablogoydfx er Gogxeuz OW, “Wipgavf Oykawunqqg.”

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.

Caoc vhorkufji ud yu isvcubutt biyuhq beivnm os o pgiu vemhnuuj.

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.

Xap ujehmte:

final list = [1, 2, 3, 3, 3, 4, 5, 5];
final range = findRange(list, value: 3);

meqtNaswu vlauhl feboxf Zuydi(2, 7) petre pjinu exe nwu fgony ecd evf etxaxaw sey bfo zanaa 7.

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.