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.

Each step effectively removes half of the comparisons you would otherwise need to perform.

In the example where you’re looking for the value 31 (which is greater than the middle element 22), you apply binary search on the right subsequence:

You continue these three steps until you can no longer split up the collection into left and right halves or until you find the value inside the collection.

Binary search achieves an O(log n) time complexity this way.

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

Here are a couple of comments:

• You use List since it allows random access to any element by index.
• Since you need to be able to compare elements, the value type must be Comparable. As mentioned in an earlier chapter, users will need to specify List<num> for integers rather than List<int> since only num directly implements Comparable.
• binarySearch returns the int index of the search value if it’s in the list, or null if it’s not.

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;

Here are the steps:

1. start and end are the indexes of the range within the list that you’re checking. As is common for range indices, start is inclusive and end is exclusive. That is, the end index is one greater than the index it refers to. This makes it play well with length since the length of a zero-based list is always one greater than the last index.

2. start and end will keep getting progressively closer to each other on each iteration of the loop. If they meet, you’re finished searching.

3. Next, you find the middle index of the range.

4. You then compare the value at this index with the value you’re searching for. If the values match, you return the middle index.

5. If not, you update the range to either the right or left half of the collection.

6. If the while loop exits without finding a match, the value wasn’t in the list.

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

Run that, and you should see the following output in the console:

indexOf: 7
binarySearch: 7

7 is the index of the value 31 that you were looking for. Both search methods returned the same result. However, binarySearch has a fast logarithmic time complexity while indexOf has a slower linear complexity. binarySearch assumes that the list is sorted. If it’s not, binarySearch won’t work. indexOf can’t make that assumption, so it has to use a slower algorithm.

Binary search is a powerful algorithm to learn and comes up often in programming interviews. Whenever you read something along the lines of “Given a sorted list…”, consider using the binary search algorithm. Also, if you’re given a problem that looks like it’s going to be O(n²) to search, consider doing some up-front sorting so you can use a binary search to reduce it down to the cost of the sort at O(n log n).

Note: You’ll learn more about sorting and the time complexity of sorting algorithms in Section IV, “Sorting Algorithms.”

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.

Your challenge is to implement binary search as a free function.

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.

For example:

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

findRange should return Range(2, 5) since those are the start and end indices for the value 3.

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.