# 21 Binary Search Challenges Written by Kelvin Lau

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

### 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
``````

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.