12 Chapter 12 Solutions

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

On each loop you move start and end closer and closer to each other until you finally get the value…or find nothing.

Good old loops can be a lot easier to wrap your brain around, can’t they? Don’t let anyone tell you that recursion is the only answer!

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

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

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

The logic is the same except for a 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).