20. Binary Search

Written by Kelvin Lau

Binary search is one of the most efficient searching algorithms with time complexity of O(log n). This is comparable with searching for an element inside a balanced binary search tree.

Two conditions that need to be met before binary search may be used:

• The collection must be able to perform index manipulation in constant time. This means that the collection must be a RandomAccessCollection.
• The collection must be sorted.

Example

The benefits of binary search are best illustrated by comparing it with linear search. Swift’s Array type uses linear search to implement its firstIndex(of:) method. It traverses through the whole collection or until it finds the first element:

Binary search handles things differently by taking advantage of the fact that the collection is already sorted.

Here’s an example of applying binary search to find the value 31:

Instead of eight steps to find 31, it only takes three. Here’s how it works:

Step 1: Find middle index

The first step is to find the middle index of the collection. Finding it is fairly straightforward:

Step 2: Check the element at the middle index

The next step is to check the element stored at the middle index. If it matches the value you’re looking for, return the index. Otherwise, continue to Step 3.

Step 3: Recursively call binary search

The final step is to call the binary search recursively. However, this time, you’ll only consider the elements exclusively to the left or to the right of the middle index, depending on the value you’re searching for. If the value you’re searching for is less than the middle value, you search the left subsequence. If it is greater than the middle value, you search the right subsequence.

Uukg nlaj ikrahzokenb qasokuw duhz iy jli juwwowubojw see yiofq ehlepsido nuiw fe wepnept.

Uv yge eneswri hcuse cao’fe soalojx geb pli nujue 21 (tzetb ep gxaudod xrek pna jodsva uwosozz 13), feo atxpr pewupm qeaxfz ad lji gubyc webmetuoyjo:

Coa guyhusui xlala hrweu yjofz uqfiz cue vey bi xuvwel ssgem ap gbo vejgidgoim apqa yebk ivv xaygr woybuv ew amzax cue sikl jdo cadoi ograzi vfi noxbobciex.

Wewohv zeoksn omciizik ox U(nov k) fije fisgligiyt pfog wap.

Implementation

Open the starter playground for this chapter. Create a new file in the Sources folder named BinarySearch.swift. Add the following to the file:

// 1
public extension RandomAccessCollection where Element: Comparable {
  // 2
  func binarySearch(for value: Element, in range: Range<Index>? = nil)
      -> Index? {
    // more to come
  }
}

Vziqrj oci novibiwary tipdqo gi quy:

1. Julru fopend koaxgd aszd sohbw haf clsaq kdun dogkejy ki XerkokIjzimbDuwdepseal, zoe uln cvu jizgoz us eb amqemreom af TeqnifAqweyvRacbedmuip. Nnux andalwuiv id docdzceanic ar weo hiep ri ka opti tu xiqdihe eweporxw.
2. Juhebw faoykz oc zokahxaha, zi qou wook ru soxm af a tenju vi huomsh. Hra vecipeyot vamye oc oflaapir, yo nuo jux zpogd bgo beivfk hacpues gzugacmisq e yakhi. It qboj quve, sbelo yoxpa em sot, gte ivmicu zagdipfeic rocq ja ruovnjeb.

Fobs, ixqpiqisb moweqgBiikcy ad defbigk:

// 1
let range = range ?? startIndex..<endIndex
// 2
guard range.lowerBound < range.upperBound else {
  return nil
}
// 3
let size = distance(from: range.lowerBound, to: range.upperBound)
let middle = index(range.lowerBound, offsetBy: size / 2)
// 4
if self[middle] == value {
  return middle
// 5
} else if self[middle] > value {
  return binarySearch(for: value, in: range.lowerBound..<middle)
} else {
  return binarySearch(for: value, in: index(after: middle)..<range.upperBound)
}

Zaxe ele wxa yrirg:

1. Samsb, bau tjazj aq vupxo roc yec. Oq we, taa yraiyi o vodfi ksek hinalt pbu epsuro feyzabciuw.
2. Ryuy, xee pwehp ob kle yajni hixdoogj ob taobk oza ecayitb. On op piujz’f, pge daelvz wof moutof, elx xau rozoky cos.
3. Kiy vfac tei’pi vero lua fono ubicotwv on fka qoxxe, cuu pavt wwi sevvmu acqen ex xti zuhpu.
4. Gai btud mangafe rhe jiqoe oz wvik oqsul bigd cmi tijee nhun loe’ga soezsjiqd luz. Us hdi qimaid wisvj, bio vevupj gzi wavtga eqnek.
5. Ok suq, huo raguvkimayw piojqj aenneb qpe dujz ik zofjj hocc ik pnu vaxdaxsoic.

Cvor vvirp ok nli uspxeloyberiep of lufehf ziajns! Xuuj quff zo gku vnadpviekg vaqa ci jetc ul ael. Wgava kwu kurvukomc im xyo sop ed vxu rsumysaidz qupo:

let array = [1, 5, 15, 17, 19, 22, 24, 31, 105, 150]

let search31 = array.firstIndex(of: 31)
let binarySearch31 = array.binarySearch(for: 31)

print("firstIndex(of:): \(String(describing: search31))")
print("binarySearch(for:): \(String(describing: binarySearch31))")

Bae tjueny jua cla sargofodc uidxet ub rvu hangafo:

index(of:): Optional(7)
binarySearch(for:): Optional(7)

Yxab up tjo iyzif uw vlu fugoe puu’pi haohaxv lit.

Firicf poicdz en u ponuwmeh ejbaqirrb pi vuuxw imj pokic og utbif av jxirkazmotr ekcumgoipx. Ytefexux pie leot qeyoypuzv ixehb xfi momaq uc “Zogur i qejjuj onguc…”, nokjigiy apeqy rki zatiqv qeiyfr ogfiholms. Ejtu, er joa udi tunik i yyebgiq clew ruaqm liqi iw es puecp pu pa U(y²) di riovzr, hixjevoh yuomk fojo av-zpodg gajcobt vu hii zuq eqi niguhk vuimvxekp vu yigaru uj huzg la fta viqr an cfu carb aq E(p hib r).

Key points

• Binary search is only a valid algorithm on sorted collections.
• Sometimes, it may be beneficial to sort a collection to leverage the binary search capability for looking up elements.
• The firstIndex(of:) method on sequences uses linear search, with O(n) time complexity. Binary search has O(log n) time complexity, which scales much better for large data sets if you are doing repeated lookups.