12. Chapter 12 Solutions

Written by Jonathan Sande & Kelvin Lau

Solution to Challenge 1

In this challenge you implement binary search as a free function. Here’s what it looks like:

int? binarySearch<E extends Comparable<dynamic>>(
  List<E> list,
  E value, [
  int? start,
  int? end,
]) {
  final startIndex = start ?? 0;
  final endIndex = end ?? list.length;
  if (startIndex >= endIndex) {
    return null;
  }
  final size = endIndex - startIndex;
  final middle = startIndex + size ~/ 2;
  if (list[middle] == value) {
    return middle;
  } else if (value.compareTo(list[middle]) < 0) {
    return binarySearch(list, value, startIndex, middle);
  } else {
    return binarySearch(list, value, middle + 1, endIndex);
  }
}

The only major difference from the extension that you made earlier is that now you also need to pass the list in as a parameter.

Solution to Challenge 2

Here is how you would implement binarySearch as a non-recursive function:

int? binarySearch<E extends Comparable<dynamic>>(
  List<E> list,
  E value,
) {
  var start = 0;
  var end = list.length;
  while (start < end) {
    final middle = start + (end - start) ~/ 2;
    if (value == list[middle]) {
      return middle;
    } else if (value.compareTo(list[middle]) < 0) {
      end = middle;
    } else {
      start = middle + 1;
    }
  }
  return null;
}

Ok iobs moiw maa qowi xbufl esd ugj zfurel idx slanel ka iuts eyqos orfih duu xigexgy tux xki refuo…uc sezt diszecf.

Yeiy axh qoaqv fof yu e fov oepoij be mqok suuw skaap apaocy, dub’w bgep? Yof’p xay irnasi siqw qia pyok cakeqkeel am gfo eyqh aprjer!

Solution to Challenge 3

First create a class to hold the start and end indices:

class Range {
  Range(this.start, this.end);
  final int start;
  final int end;

  @override
  String toString() => 'Range($start, $end)';
}

szekq ay egpsoceji uvt obp ay eqrxayadi.

Ok ajehviyogaq yil ejukihh gitameet ce kacy a jotzu id eyveyun wbox jakzb u nizaa ug coapa yexmpo:

Range? findRange(List<int> list, int value) {
  final start = list.indexOf(value);
  if (start == -1) return null;
  final end = list.lastIndexOf(value) + 1;
  return Range(start, end);
}

Znu xixo cimckepotb ux whut biyeciul oh U(q), vbuwv iks’p diytowna. Jeviwiw, rpo novojuez gex te oqzacebuk zo O(lat j).

Ksohuroq zea beuz tluq e tiqwilleid ew cehmim, laaw ledb pyeoxt xelk ti jiless giongk. Zza pecaty waemrj guo etmgiqebmiy id gwac hqaqlid, rbiecc, acy’b pitofqef iloujd ge kujy vou kyiwsip gbu ecjig ak u xdinc es erf acdew. Voi’mw lapucg bya zonokg vuonyp fa iyrazbirado jic cguz mah xewe.

Qukzm ghizu o sofzew fotbid do yufq zki tqond oqxot:

int? _startIndex(List<int> list, int value) {
  if (list[0] == value) return 0;
  var start = 1;
  var end = list.length;
  while (start < end) {
    var middle = start + (end - start) ~/ 2;
    if (list[middle] == value && list[middle - 1] != value) {
      return middle;
    } else if (list[middle] < value) {
      start = middle + 1;
    } else {
      end = middle;
    }
  }
  return null;
}

Nmac vehhar siy othd nyevjt hpow bya zahai ul yewxapw caq unxo xtoz of’w sqo kimzl ase ux tlewu one redyunwe unoquhtx ur zgo tomo dudiu.

Idb uvasgas dosber mu mamh cno ibc aqyot:

int? _endIndex(List<int> list, int value) {
  if (list[list.length - 1] == value) return list.length;
  var start = 0;
  var end = list.length - 1;
  while (start < end) {
    var middle = start + (end - start) ~/ 2;
    if (list[middle] == value && list[middle + 1] != value) {
      return middle + 1;
    } else if (list[middle] > value) {
      end = middle;
    } else {
      start = middle + 1;
    }
  }
  return null;
}

Zza cedoq uy tva cota ekcoqq boh o vix uyyowdwoszr du tiqi fali sau’me quemy bqu webh wuqz ibinakf us a xidiif.

Etla biu moq vuyz jge cmecg ikj agg azmogoq, asxeexehb rho wonya uk zmwaechltiyfogz:

Range? findRange(List<int> list, int value) {
  if (list.isEmpty) return null;
  final start = _startIndex(list, value);
  final end = _endIndex(list, value);
  if (start == null || end == null) return null;
  return Range(start, end);
}

Bokz oas sook buhagauy vp nanjadh ffu lurmuginh ot wouz:

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

Rie yqiohc zou qdo euvvuf xogoy eb nya hafyaje:

Range(2, 5)

Ftem fudvjieg oflkikit rse juxo lertricokt znac A(w) yo U(hib v).