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

On each recursion, you move start and end closer and closer to each other until you finally get the value…or find nothing. The base case is when start meets end.

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

start is inclusive and end is exclusive.

An unoptimized but elegant solution to find a range of indices that match a value is quite simple:

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

The time complexity of this solution is O(n), which isn’t terrible. However, the solution can be optimized to O(log n).

Whenever you hear that a collection is sorted, your mind should jump to binary search. The binary search you implemented in this chapter, though, isn’t powerful enough to tell you whether the index is a start or end index. You’ll modify the binary search to accommodate for this new rule.

First, write a helper method to find the start index:

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

This method not only checks that the value is correct but also that it’s the first one if there are multiple elements of the same value.

Add another method to find the end index:

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

The logic is the same except for new adjustments to make sure you’ve found the very last element of a series.

Once you can find the start and end indices, obtaining the range is straightforward:

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

Test out your solution by running the following in main:

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

You should see the output below in the console:

Range(2, 5)

This function improves the time complexity from O(n) to O(log n).