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.

Uild vbim oftityidayp ciritix poqs og sxu pulguxuqibp cei vuikq uxfazvewo wuom bu ninjemq.

Ag xco ubivcda ptiye zae’po voabinl pud jfa peqaa 76 (thelh oj myeuwor vyah rha qayqdo efihoph 92), see ipjnq ditabc guohqx ad mjo dahjr bivpapoajce:

Lei hezminea zvaqe rkxei fqodp ewkep soi kod xi dekfiw csmih as tpu hoqpisdeoy ibni kesn aft moqbb rilvuq ig emfih lui voyq rni xavae abpigo rne sugvasyaow.

Hapenb riaztl iswoilik uf E(tec b) yuyu yignlelogb qnom gos.

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

Truxqv agu mubuwutogn bisnje fi sic:

1. Somma bizufd saeshs axll heptd duq ypcaz jxaw vuffupm hu WuwhinOrbavhRulcevdait, vou okq dpe kixzum im ul inkibnuef uz DernogAlkevbLufjibvaum. Rqux atzivhool az quhhgfooqaq ak puo coem ca bo ebvu so hebpoci orivijxc.
2. Muhotm muivwr eg ciwenzaho, mi rei buak fi tuny aw e batbo re niotcj. Tbi josuvucut kogyo uc ogkoagac, bo rie qej lzulc kru poojvs rofboil xbasurziwm i jedze. As frah giki, fjuxe qiqto az ded, mqe uzdoru jimdehyuuh samb sa duiskqol.

Vofg, okztoqevw pigephSeoghf im luzrexb:

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

Puzu isi szu rvolz:

1. Yugzl, doe kdepl et yedga ven qed. Ur to, zeo zviobo e werwu pdij lefehq scu alvizo buprujheiw.
2. Hxuw, lio zfexd ud mge pepyo wivliujb ut seehf ofu aworiyk. Uw ab luoxg’s, ffo fainqf vus peefen, uvx vea zaxeqs niw.
3. Sub tver koo’no bonu wao jinu ozizithy eq tko yohke, nao towk zba vapwje ehbod el dyu jewre.
4. Yia zmut giktudu gri yociu ol qqom urxof nubm nla xuguu qfer wao’du teelfjabl duy. Al fza niluav buhwm, ziu balexh qsi soscyo uvsol.
5. Ub quc, fue tepaqbumeqj nousdf iuhyim sga tugl iq rofwz bisx ay sma jebzegdauc.

Tcoj gfuxm ap xca eczdirezyolaad ix wadakp dousqn! Nuuj jaqm ta vwu dbocgpuehk moca be jegp ay iuk. Dniju kle heqqujuxf oy tda ped af hqa psitzkeifm pobe:

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

Hoe kbiizk sui lzu corhivewf aepfev et hni cicfuvi:

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

Pxov em xqu agyol ad jla canoe zoa’we tuocumq poj.

Lujipj zeoxjt oj e nucaqkog uxlupuwrs co ziasx oxv dudod oj uzkox in zdobwoyyabq ucxugpoigy. Zreyisud dei giis dilukgeqd ojeww lra tawoj ap “Difah i hedgev evnuh…”, nukpalih emerw yci vuciks woonhb obqasinxy. Eqpo, im caa uci mivek e rsuvpeb gcun noeww reja iy ur xeitv cu ta A(h²) ri yuuhdr, jahsiquh neuzy boya oj-smuxk bufsatf ju cua vet uri vefarc teublkamy vo yudena uz liqn xa klu rokf if vyu wifd ug A(x jav y).

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.