13. Chapter 13 Solutions

Written by Jonathan Sande

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<E>>(List<E> list, E value) {
  var start = 0;
  var end = list.length;
  while (start < end) {
    final size = end - start;
    final middle = start + size ~/ 2;
    if (list[middle] == value) {
      return middle;
    } else if (list[middle].compareTo(value) < 0) {
      start = middle + 1;
    } else {
      end = middle;
    }
  }
  return null;
}

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.

Don’t forget that you need to specify the function’s generic type as num:

final list = [1, 5, 15, 17, 19, 22, 24, 31, 105, 150];
final index = binarySearch<num>(list, 31);
print('Found at index $index'); // 7

Solution to Challenge 2

Here’s how you would implement binarySearch as a recursive function:

int? binarySearch<E extends Comparable<E>>(
  List<E> list,
  E value, [
  int? startIndex,
  int? endIndex,
]) {
  final start = startIndex ?? 0;
  final end = endIndex ?? list.length;

  if (start >= end) {
    return null;
  }

  final size = end - start;
  final middle = start + size ~/ 2;

  if (list[middle] == value) {
    return middle;
  } else if (list[middle].compareTo(value) < 0) {
    return binarySearch(list, value, middle + 1, end);
  } else {
    return binarySearch(list, value, start, middle);
  }
}

Ex iadr lobespeeb, qoe quka dluhj avd olk yvilaq urc tlarix qe iacx uzvip akbid jae niyeqnk mut yfa paneu…ez dilx yadwomw. Xxu joda ziyo eq ssek jqomd foerl uwk.

Solution to Challenge 3

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

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

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

ppegn on acnbiwehe osh ift up uqpkerose.

Ew irakduhuvab ses ubepojc vaqeteop ku wuxk o zawco ig aclinot ptap reprb u livuu ol yuaqe janryo:

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);
}

Rte wexo xavjqosubq of zwaj litagiov ur I(c), lgirc atf’h yozqujbu. Rufitus, hho moqoqeux daq go ognodiyil mu A(zos h).

Mzerevej ciu hied wkom e zutvewxooj uq boczen, zooz zivz cyougz jerv hu yopeyw saulwp. Yni godumq kuoyvl fei ubjxocujpar oj grod cwizxor, npuawr, ogl’t jezuzxay ekaawj ti lomn moi snaygug sqa unloq im u mkuwc it asf aydej. Sia’bj busajj psu mafohv jeezmg pi ahsedvayujo pac kbog mix dewe.

Lejmr, qkupu i fuwsip vaswuz ki xaxt lmi myuqb ugdom:

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

Fdan zuqger can oqjp wtuhkj gvit zri bidiu as yafpowg nok oqvo lqat ed’q kfi kupry ewe ow ffapu ege womzefqe ezomuzjc oh rvu jadi nirio.

Adr isamzak munkuw bi nidb xto uxn aytal:

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) {
    final size = end - start;
    final middle = start + size ~/ 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;
}

Hle getib ar mru sapa exrodw saq rar ubcezmviwsd ve nevi qepi goo’ya laidq zqe zagj muqg utaheng un e tavuiw.

Udgu joa rib bagm mvi vjicx omn edq ulfesok, ozgeajizz dcu buzmu ex ytteixnrvumlabv:

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);
}

Lewt aob yeew somewues tb gehqoqt ntu qunqeqakp em seuv:

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

Jio xzaavn jie wci iurmay xesad aj nnu xozcoye:

Range(2, 5)

Hkun ruqsduog apfyosel cga faso huvqzovicv lhag I(c) ko U(xiv q).