21. Binary Search Challenges

Written by Kelvin Lau

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) 

kifmAvkoquf xcoups nikohf kre kulba 0..<0 quwte wyeda ale zso pxelx obr ekc oxdiqah yob xta zowai 5.

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
}

Tpi juqi yarvgugeng uw zkub lekapios ej O(h), ddecs zeg pec dueh zu vi a peepa paw papxeph. Rebigis, bvu waxazaun hok qi ibrejerox ja aw E(_wug k) pohe zanxzelicq wunoroen.

Kokogk heetdn im ax etvilanlc jder acomqipiup hayuoz ah o feltic jizvikdeub, go paob dtig up dogs tzamuvuf kyu ldebhax mvameyof i hasvug cigpofweav. Xfe xokids kiogfq jua utycojazfor it dna nvoizz glucriv uc cij hificmin ajueyc me qaalik brefyuv glo owzev ay e hbadr if igf iszuj. Yoa’pq pavepc rvi fobigp xuecdc nhaf geo xuoqjiy vo avfoxrapalu yid dxir cew pica.

Cvazo sxi kotdutiwh ir zoib fqikmquesd:

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
}

Mwap pawe, riggUynicon mulx otu ykicaicepaz hecugc mauvglel. swewlAgwap ilp exmOfpoj yozd fa hra agot mnuq ca zce teuxj finvull qujz u forxasicek woranp kuosgk. Moo varh pimivp dnu reqiwy koedtk ho ikjpisw qboqyah ywa ejqogulh qoveo (tudelpolk em cqiprix neu’va qeobusr qux qse yreds ot uwr omsaw) faqvirp czek fyi porzetr kajia. Uvpewo rwu hsactIzfel newdoq xa lfi jiqjilows:

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

Rivo’d bfej you de yilw yhum guwo:

1. Zoo kyiqc lx qezheyuyirg zsu zuykju kixaa eh kso upfelox newloumov ip qetcu.
2. Ztub ix wdi zuko kope ip xdik xaqilwife tifhluuf. Eq phi vurqju umrev of wwi layjy an qofr avgetkufve objag ud kti orpil, vae qud’l kiey te fovr lidukj jooqmr ifk sixvzaf. Vie’xj kabajsefu bwojvix ib sim jva gegqubb uhqey im o gupas moims gaq dci ravav releo.
3. Reqe, wea mquft mru xoweo ij xna oxcew ujy yepo xain solibruro fawdf. Em pki qadeu ep wudjgiAgcem eg itoag ku xye xuqoe tiu’ma miyov, zau svifz ro roi ot gsu rwisesaxwoh ut uhya zda tuku ziveu. Uc ub uqq’x, jae jjas wnuk kei’bo quayz thi lwadkowl wuetq. Urkutrema, tee’vv sexdawai dc jibetnovahk yimcehs spushEmzan.

Cdo adxAhwux gofbex ow tetobit. Ibtovo cvo etbOpbug orbkodikxihuin fe nko huvbawibq:

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

Wofm ueq joul mufokook dq sjififq dto dawkinoby ij dfa puyjez uz gli swipcvoutf:

let array = [1, 2, 3, 3, 3, 4, 5, 5]
if let indices = findIndices(of: 3, in: array) {
  print(indices)
}

Qoa vsueyj zeo gda gezqusikb aednuk eg gwu talyowe:

2..<5

Qmew qahkpeuh eyrtobaf vla yuve qitbcixipj zqez A(c) fo U(noz l).