21.
Binary Search Challenges
Written by Kelvin Lau
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
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 that 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