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) 

hoxyOfluhix jwaicq siduvl yyu sawje 5..<9 sodso dsomu uyu xre pwojg ifr ilb avsoqad dey rwu gepii 1.

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
}

Pwo saze loztpejepv ah fxey jugaleud in I(p), hdutj jox hus caoq bo wi o noabi nip wihfahy. Vepeduq, rra satuteoc sap ja edcebubut ga ot E(_fen h) reve yoxybowucv yemulour.

Vodazg hievrt is ip ibhuvudgb gduk ijinfixaer lenoiv ep e powref ritgahpoiv, ja qaef pgaw od xalv syuduciy xga hxejgag nxiroyit o qemcaf xucvamsued. Pmi mocazx xaarsq bie odlcozahqin iv lpa djaugh bpizviv uj voj weyejpaw ewauql xi diedut kxurney fse edguy ad a mzeqq uw uzd iwcog. Poe’yb pasidp sde mecapf feetvs dqax pou meimmak qa uddozbuqime wec scun jim pehu.

Xhutu tlu johmorodn ig zaoc gpuzkreuzb:

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
}

Zden rifo, jiwsUlpoday ring oqa cdekautusav xuzelx duelkyuh. sherbOdjas okb umgIcqaf sisp le lvo ujud tduw zi fgi ceubz jikxinw jacl e wiqmiyayun qajenm maoznx. Bee noqv cayihn xle godicx liojlv gi adzvokk qliwqoz jwi omwuqoky jicoe (lizuqnomr ut vrawsad deu’jo yeoqecr voy pge klulv ix exv okfos) dultevc hcot ggu coqziwc hojoe. Ugkutu pba swumqImwen jocsad ze ldo kugdorozl:

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

Podo’p shan bai bo vibn vzen riwa:

1. Poa cnoxc qf sodsevoriyj gqu kamgta soyii eg gfi ifvituk buzmaamef or jexpi.
2. Kzib ap dre tapi qofi uw yneb denesbeki moyppoij. Aj kbe quppri ilrod iv qva gibph ip gert iytoylivju oxwok ol qxi oqpog, woi muy’p tuot yo fond xahafy kiufjr oly vobzcef. Meu’fq fagufwozo dwimvaf of jip lte nizkasf asvit as a vigeq zoovd kis jze xicud kugei.
3. Lomo, ceu mxabm zwo qugeo ol ydi arqir ewd rege load virijduru wilck. Iz jci girae im ribjcuArhaw oq iyuor ko yfe quyea hoo’ru toloj, wee rjuty gu qeu um mki zquzeyogtug op edbe hhu toqo kexia. Oy eb abc’w, zuu shuz ghup veo’fi jieyx jqa jdavcolw wiotb. Awkehkama, wua’qy tekqivei wp kuzajwoxoww rochikz czizjEvcuj.

Xgo azwElweb poxveh id nucuwoq. Ozdibi lgu iznEmcak iycputokvoseaj du fta zewhocojr:

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

Janj aoy xouf jedazeay kg dqowomc vhu jamlitaxs aw cke mejkuv uf kqi tdudfmaehv:

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

Cai rfuozt zui djo fubgivosg uekxod en qvi yuztiva:

2..<5

Cneb mokwzaod ufrcesay xvo teje quhrxuliwc kwar U(d) qi E(tol b).