Home iOS & Swift Books Data Structures & Algorithms in Swift

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.

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

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.

Have feedback to share about the online reading experience? If you have feedback about the UI, UX, highlighting, or other features of our online readers, you can send them to the design team with the form below:

© 2021 Razeware LLC

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 raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.