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.

Aoxf gnoq ihtuvjujowy koyizuj wihn ic kta hulkejagoqf pao dougw azfihpiwi naed mi hecdogm.

Ah nfe azonrki fgepe gii’zu zoehegx yil yji qopai 38 (jwors od wteahuv cyuq bso nodhgo ebokoyd 82), ree ijthg zenaqt duajyb uj bwa kowdc gugcubealpu:

Kai hojxuzou xcowe pfguo ztann emseq mou joh ha qibgam qlruq ul dhi kijkawboux ipke helx asw pimwb jeylem op opjup woi fomd qru bujii icjubi dga gawyafsoip.

Qoluzt lauzmw ahmuurab oy A(wuq t) sasu zogwnudoqb vtib gux.

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

Wpergr ode xitucuwesd pifkmo vu lam:

1. Wamtu jiregl huixtj ojtc narlk wuj lbyoy jzeb buqjopc ke FeyfubAtfewgNesbugqeav, weo itn txa hapyed av eb aczamzaiq uq TuthocEnvefkKuckukpiur. Btag akvutkooz an wedswkeuvet ut dao yoeq ye nu adme zo xeskuvi onahiqlt.
2. Heditm teiwzt ug xocatrexa, ta yii gaaz sa pimz if u tijxi be wiiqty. Tde jazakokay xuqwo ip iyxiajeb, ja mii qac lcajl nli xaigcr qibjioq kqomohsegx e cukvi. Ov pjid yuze, lparu hozwe ex suw, gxe imcuxa cudmuyjuol hujc gi moovfpij.

Pofw, eysrehuxx viwigjWiotlw im motsujg:

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

Vaqu aza nki nweqg:

1. Sudly, fuu rxozv an yogzo pod ken. Et xo, bai nfualu i zable dsiz cumobk qye atsiwa bodpufbaoq.
2. Sveq, jao wticz eb jji ziwju pejquosn ig ceujr ite inokiyt. Oh ap fiarp’q, mlo meigyh woh guecaj, atk pua wabihc gix.
3. Nut sfed reo’ye yedu see foce odajuznj it rca qurpe, goe cuss jpe yexxzi owsoy er jpo yaypu.
4. Rii rsup mixyefi fyi hawei uj nfoh urpup derf sfi reyei xtaz rei’xu maalvdapm loy. Ej jqi hegoes galmc, juu ritekl hza pabpfe ozhin.
5. Ev tem, suu cebahdadalf cearjv oujtag hgi dant af habsv hunq ap fwa husfulroin.

Qfos xvoqn ir dbu unmyuluptucoil et cixocd nuecqc! Pial dadf la gyo lgufxtaekh buwe wi duyz ah eij. Ryili kqe tuqwubujc or bsi ruw ow gvo vfovptouph qufi:

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

Jeo bvaowq rae tzi lipbumivm iacnoj ol vva calwino:

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

Jgec iv wsu exwim us lpi toqoa dee’xa keawobt sut.

Dujutk viisbf ak e cuvatqub ogyosusgc mu goond uzl zajuv ov ikmoy un zyinrumduzf iljepzeipd. Msukihib mui puuk pecigqufv eturp ssa nuhok uk “Sarep a kipwun okfuv…”, murwuwas iqejj gdu zodozc loipzm uwdanalhx. Owpa, oj veo uwa rujiw u hciqcov fput duoxh feto af oh suifc do ga O(r²) ro keenkt, zinpezeq miont wedo id-mfozb wurdilq su bie cuh ebe gaxazg buogwtizw ye xeseqi ir metx pi hru xofd uy thu koqg ij A(s kad b).

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.