11.
Binary Search
Written by Irina Galata, Kelvin Lau and Vincent Ngo
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
Binary search is one of the most efficient searching algorithms with a time complexity of O(log n). This is comparable with searching for an element inside a balanced binary search tree.
Two conditions need to be met before you can use binary search:
- The collection must be able to perform index manipulation in constant time. Kotlin collections that can do this include the
Arrayand theArrayList. - The collection must be sorted.
Example
The benefits of binary search are best illustrated by comparing it with linear search. The ArrayList type uses linear search to implement its indexOf() method. This means that it traverses through the entire collection or until it finds the 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 middle index
The first step is to find the middle index of the collection, like so:
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, you return the index. Otherwise, you’ll continue to Step 3.
Step 3: Recursively call binary Search
The final step is to recursively call binary search. However, this time, you’ll only consider the elements exclusively to the left or 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.
Implementation
Open the starter project for this chapter. Create a new file named BinarySearch.kt. Add the following to the file:
// 1
fun <T : Comparable<T>> ArrayList<T>.binarySearch(
value: T,
range: IntRange = indices // 2
): Int? {
// more to come
}
// 1
if (range.first > range.last) {
return null
}
// 2
val size = range.last - range.first + 1
val middle = range.first + size / 2
return when {
// 3
this[middle] == value -> middle
// 4
this[middle] > value -> binarySearch(value, range.first until middle)
else -> binarySearch(value, (middle + 1)..range.last)
}
"binary search" example {
val array = arrayListOf(1, 5, 15, 17, 19, 22, 24, 31, 105, 150)
val search31 = array.indexOf(31)
val binarySearch31 = array.binarySearch(31)
println("indexOf(): $search31")
println("binarySearch(): $binarySearch31")
}
---Example of binary search---
indexOf(): 7
binarySearch(): 7
Challenges
Challenge 1: Find the range
Write a function that searches a sorted ArrayList and finds the range of indices for a particular element. For example:
val array = arrayListOf(1, 2, 3, 3, 3, 4, 5, 5)
val indices = array.findIndices(3)
println(indices)
Solution 1
An unoptimized but elegant solution is quite simple:
fun <T : Comparable<T>> ArrayList<T>.findIndices(
value: T
): IntRange? {
val startIndex = indexOf(value)
val endIndex = lastIndexOf(value)
if (startIndex == -1 || endIndex == -1) {
return null
}
return startIndex..endIndex
}
fun <T : Comparable<T>> ArrayList<T>.findIndices(
value: T
): IntRange? {
val startIndex = startIndex(value, 0..size) ?: return null
val endIndex = endIndex(value, 0..size) ?: return null
return startIndex until endIndex
}
private fun <T : Comparable<T>> ArrayList<T>.startIndex(
value: T,
range: IntRange
): Int? {
// more to come
}
private fun <T : Comparable<T>> ArrayList<T>.endIndex(
value: T,
range: IntRange
): Int? {
// more to come
}
private fun <T : Comparable<T>> ArrayList<T>.startIndex(
value: T,
range: IntRange
): Int? {
// 1
val middleIndex = range.start + (range.last - range.start + 1) / 2
// 2
if (middleIndex == 0 || middleIndex == size - 1) {
return if (this[middleIndex] == value) {
middleIndex
} else {
null
}
}
// 3
return if (this[middleIndex] == value) {
if (this[middleIndex - 1] != value) {
middleIndex
} else {
startIndex(value, range.start until middleIndex)
}
} else if (value < this[middleIndex]) {
startIndex(value, range.start until middleIndex)
} else {
startIndex(value, (middleIndex + 1)..range.last)
}
}
private fun <T : Comparable<T>> ArrayList<T>.endIndex(
value: T,
range: IntRange
): Int? {
val middleIndex = range.start + (range.last - range.start + 1) / 2
if (middleIndex == 0 || middleIndex == size - 1) {
return if (this[middleIndex] == value) {
middleIndex + 1
} else {
null
}
}
return if (this[middleIndex] == value) {
if (this[middleIndex + 1] != value) {
middleIndex + 1
} else {
endIndex(value, (middleIndex + 1)..range.last)
}
} else if (value < this[middleIndex]) {
endIndex(value, range.start until middleIndex)
} else {
endIndex(value, (middleIndex + 1)..range.last)
}
}
"binary search for a range" example {
val array = arrayListOf(1, 2, 3, 3, 3, 4, 5, 5)
val indices = array.findIndices(3)
println(indices)
}
---Example of binary search for a range---
2..4
Key points
- Binary search is only a valid algorithm on sorted collections.
- Sometimes, it may be beneficial to sort a collection just to leverage the binary search capability for looking up elements.
- The
indexOfmethod of arrays uses linear search, which has an O(n) time complexity. Binary search has an O(log n) time complexity, which scales much better for large data sets.