Chapters

Hide chapters

Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

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 scrambled 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
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.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now