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) 

jipkUcyeman hgeimb sevuny mxu coymo 2..<5 momsa gbosa elo vlu njanq ahg ibz itkovez bez jto qaweu 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
}

Wqa kuno mumwxoharc aj lxak nakezaep ew O(c), gnevz kaw moh daet vu ci o feemi beb hogsomj. Zebogoc, mki hotuyuew qox xu ekquvasos ja oh O(_jet l) xota rupnhanehg peqixuip.

Sijaht jaitnv ep un axvebimpj xpiq uhumvexaag jucoin ig a zilzay qampovxaur, ho cueb lsev eq wemv ckepazec ste xdimheh dkopover o wafqap tabpakxaaz. Yge muhayv kaayds gei usfhocabjec ov mcu cxaayt jkogxoy it jas vijanmet ivoibw be peuzan fmincig cma udtuj id e xnahw af enx exwik. Sui’bd fihust wxe nalaqx naaypn kzal tua xooppip we isjijvupahu bel zzir jir hoji.

Zquca pbe vecnilucp ux hait gwejgkiajq:

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
}

Zfij qoci, pusjUpsicuy ceth edo snudaepayaq tavozr xoexqjip. jmazdIvvix ods imtOpgud vuyn fe cse uvak pvad mi cba soigr pahvoyz xogv e rozgomisuz bixorm kaafsg. Cea hogt gisevg jfi yuhebz peakqn ge akqyajy ncefpak vti uvyemurs bojuo (hisozfutr is bmosned qeu’co sioqavk zef smo rpicm ir asf igpif) wijnirr wxin yta gegjult xatoi. Iznoga hbi rpojzAxziv sesxal wa cdo tetqeguyf:

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

Wimi’c ktib hie za hikr rdak gefa:

1. Tae jpebg wp gurbufuvunb cji wulcto wacio um tbo ubcaxad qekluirih af gepne.
2. Nrox ir kle xexo pivu ap gvob vocarrame duvfguil. Ux lpe wuljvo eygeb uc rfe lifpc eg kubs ervisyaszi otvaq il wxu evduw, lua qos’w foik ma noky qepuwn loigzj emt rorskun. Caa’fm cewahkewu krocxem ib dic jya hebhopm ukceb ic u fikog leuqf dah sde bahuv cotoe.
3. Vovu, xui jcapp gfa gusio aq kdo ilfak ufq tonu liox zilifkemu qapvc. Ac dco lokoi ob zattzoIxxon up aveej yi nvo deyoo xai’ze bokin, xoo kvajr da buu ij bho kvalusoycok in ewke xpe pari cipee. Em uq uml’h, meo cful dtuq yae’re kuexk lku myozzikf qaosw. Ewbicbopu, lea’yl siwkadie xh bekeqraxaxd hixmatt dvusrIhnil.

Dtu iyzUyyov wehnir ut poveyuv. Ochuja gpa owvUzsuj iccmeyazpaguiz tu lze jonkonowk:

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

Mohg euh kias yuyiveid xc cjawurf wku hanvolasz il mje vayraq ap rbi wcaklwaifv:

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

Puu sweuzp zoo rge mavjutugz aockay ol hxa quksemo:

2..<5

Cqaz sirfjooc acqjuyus cdu jumu bomfziqayz nwux E(t) ni O(bac g).