21.
Binary Search Challenges
Written by Kelvin Lau
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as
text.
Challenge 1: Binary search as a free function
In the previous chapter, you implemented binary search as an extension of the RandomAccessCollection
protocol. Since binary search only works on sorted collections, exposing the function as part of RandomAccessCollection
will have a chance of misuse.
Your challenge is to implement binary search as a free function.
Challenge 2: Searching for a range
Write a function that searches a sorted array and finds the range of indices for a particular element. For example:
let array = [1, 2, 3, 3, 3, 4, 5, 5]
findIndices(of: 3, in: array)
Solutions
Solution to Challenge 1
In this challenge, you’ll implement binary search as a free function. Here’s what the function looks like:
func binarySearch<Elements: RandomAccessCollection>(
for element: Elements.Element,
in collection: Elements,
in range: Range<Elements.Index>? = nil) -> Elements.Index?
where Elements.Element: Comparable {
let range = range ?? collection.startIndex..<collection.endIndex
guard range.lowerBound < range.upperBound else {
return nil
}
let size = collection.distance(from: range.lowerBound,
to: range.upperBound)
let middle = collection.index(range.lowerBound, offsetBy: size / 2)
if collection[middle] == element {
return middle
} else if collection[middle] > element {
return binarySearch(for: element, in: collection, in: range.lowerBound..<middle)
} else {
return binarySearch(for: element,
in: collection,
in: collection.index(after: middle)..<range.upperBound)
}
}
Solution to Challenge 2
An unoptimized but elegant solution is quite simple:
func findIndices(of value: Int, in array: [Int]) -> Range<Int>? {
guard let leftIndex = array.firstIndex(of: value) else {
return nil
}
guard let rightIndex = array.lastIndex(of: value) else {
return nil
}
return leftIndex..<rightIndex
}
func findIndices(of value: Int,
in array: [Int]) -> CountableRange<Int>? {
guard let startIndex = startIndex(of: value,
in: array,
range: 0..<array.count) else {
return nil
}
guard let endIndex = endIndex(of: value,
in: array,
range: 0..<array.count) else {
return nil
}
return startIndex..<endIndex
}
func startIndex(of value: Int,
in array: [Int],
range: CountableRange<Int>) -> Int {
// more to come
}
func endIndex(of value: Int,
in array: [Int],
range: CountableRange<Int>) -> Int {
// more to come
}
func startIndex(of value: Int,
in array: [Int],
range: CountableRange<Int>) -> Int? {
// 1
let middleIndex = range.lowerBound +
(range.upperBound - range.lowerBound) / 2
// 2
if middleIndex == 0 || middleIndex == array.count - 1 {
if array[middleIndex] == value {
return middleIndex
} else {
return nil
}
}
// 3
if array[middleIndex] == value {
if array[middleIndex - 1] != value {
return middleIndex
} else {
return startIndex(of: value,
in: array,
range: range.lowerBound..<middleIndex)
}
} else if value < array[middleIndex] {
return startIndex(of: value,
in: array,
range: range.lowerBound..<middleIndex)
} else {
return startIndex(of: value,
in: array,
range: middleIndex..<range.upperBound)
}
}
func endIndex(of value: Int,
in array: [Int],
range: CountableRange<Int>) -> Int? {
let middleIndex = range.lowerBound +
(range.upperBound - range.lowerBound) / 2
if middleIndex == 0 || middleIndex == array.count - 1 {
if array[middleIndex] == value {
return middleIndex + 1
} else {
return nil
}
}
if array[middleIndex] == value {
if array[middleIndex + 1] != value {
return middleIndex + 1
} else {
return endIndex(of: value,
in: array,
range: middleIndex..<range.upperBound)
}
} else if value < array[middleIndex] {
return endIndex(of: value,
in: array,
range: range.lowerBound..<middleIndex)
} else {
return endIndex(of: value,
in: array,
range: middleIndex..<range.upperBound)
}
}
let array = [1, 2, 3, 3, 3, 4, 5, 5]
if let indices = findIndices(of: 3, in: array) {
print(indices)
}
2..<5