12.
Binary Search
Written by Kelvin Lau & Jonathan Sande
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
Unlock now
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 of these 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: Recursively Call Binary Search
The final step is to call the binary search recursively. However, 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 is greater than the middle value, you search the right subsequence.
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<dynamic>> on List<E> {
int? binarySearch(E value, [int? start, int? end]) {
// more to come
}
}
Writing the Algorithm
Next, fill in the logic for binarySearch by replacing // more to come in the code above with the following:
// 1
final startIndex = start ?? 0;
final endIndex = end ?? length;
// 2
if (startIndex >= endIndex) {
return null;
}
// 3
final size = endIndex - startIndex;
final middle = startIndex + size ~/ 2;
// 4
if (this[middle] == value) {
return middle;
// 5
} else if (value.compareTo(this[middle]) < 0) {
return binarySearch(value, startIndex, middle);
} else {
return binarySearch(value, middle + 1, endIndex);
}
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 = [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');
}
indexOf: 7
binarySearch: 7
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.
Challenge 2: Non-Recursive Search
Does recursion make your brain hurt? No worries, you can always perform the same task in a non-recursive way. Re-implement binarySearch using a while loop.
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.
final list = [1, 2, 3, 3, 3, 4, 5, 5];
final range = findRange(list, value: 3);
Key Points
- Binary search is only a valid algorithm on sorted collections.
- Sometimes it may be beneficial to sort a collection to leverage the binary search capability for looking up elements.
- The
indexOfmethod onListuses 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 are doing repeated lookups.