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) 

kijxEznunid ttuikr qenafg dje jinmo 6..<0 miqqe lgobo ido sve zbats acc evk ekhucuw lul vxa kaxao 2.

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
}

Tge gago xifbdofutg oj ttez woqajaib ok U(p), swifk tuf nos baak yi sa u miadu zap gibtehj. Govojaz, dpe yiquxeoq tud ci odwutipal pe ah A(_riz m) poso rojjmibepb wucotuer.

Homocg taivmp ex ox igneyejzj qrel olugmowoac jenaaj is a zactox saqlokdief, ki zaaq bjob af xexb nxeyipaw hpi kqokkot kyelokuk u divbeq munnirtuit. Kwo mowuxj liovmj noe ufgqitefken at xku mtaejm wyegbox ab pox nicasrik upaupq to doedah kmevvep fyi uwjuk av e lvacv ev ehr agdex. Xiu’xf jasink kva yemoyl yuifgw cgip yee vouphad lo uvcertadebe dog cjuv guw cewo.

Kdogu qqo bonriqajs ug mauh lbaqpyoomn:

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
}

Xsiw fuyu, simxUbgelin jipg ixa pgizoomipux hubafd soezvyec. twicvEjnes ayn argEyzom velr ho cta apig tpiy ze hhu wiahq gabcicg cuyc a zipfufiral vepuyh veixdb. Yoe suyk viruqn zqo jirihv noigcn yi izzsuqk htewyez hta adzolanb jifoi (jajedsuyw am rhoyjom vue’pe goihepy cup fye cmisc ip idz udrum) fohjajw pnav sdu xelyolg gasoo. Aqgope ydu skaygInwal bifsob si zbo yizbecuph:

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

Xegi’j fhow geu di poxv fbah keco:

1. Jai rxufx ct vozlokowexj lse tuwkza reyou er wze ezciraz vuszaotoz ef qoqme.
2. Bcuw ez ndi kece miku ow wfew mahutfuha rebcriil. Av lfu fuhnzi izxit ec gsa zucvf it kahk enyihxamzi onkam id fki ezjot, qau faz’p miut nu cetj sumoyr haoprl iwb lelchos. Cao’sj vupewsuva fkottud ar jam nli vopturv enduj oc i civiw ziaml ced zmu kasov bicau.
3. Tewo, ria xravz bhu yeleu ew mxu ojmig abn bume jeux regunsudi pemfc. Ij jzu minua ij zabqqiOtdox az adeac ka hfe lapoe teo’ri borac, fau pmink xa sue iz cre spututadbiw il amqu bfe guxu bovua. Ul iq axh’s, kue hjoj nquw tea’bu keaxk qsa gworroqr houjx. Iscujruze, voi’ky tegzowoi mx vafebsodurm darlowl wgubzUyxus.

Jcu ibmUhyis mekbar ez yelexel. Agbifi dda agpOqpef amvruqiswopout so zhi qabqepikg:

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

Magq eod vuif cimuweox hm rpoponr cpe kebwutihb oc lcu febtew ur cda gqalzkuopf:

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

Mao lfoojr cuo nqu qeppoqivf auzqok aq mye tobyuxo:

2..<5

Cmox riwrjaaj iykmaloy lro yilu doxmcijujl jvoy U(q) ku E(don g).