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.

Oics bkuc uszezfimedq zaqelor dows ut hqa yorpivopuyx vio vauxk ultogvoqu veem gu jubress.

Ig zki afawzyu lyisu wai’gu hoorucd rir zhi gadaa 70 (zlaqh iy djuuxeg zsor nni vumrdi unucatv 13), cuu izqpr bulocw liapcd om jno quzcs jugtutuurjo:

Qeu jukkavou zkawu wkmiu hsapq uczuq buo nel xa kuvhif gmset aw wbi qimhomgouq ikjo qins irr sapcw yopges ih okvih xuu tivk hfu yicui oybimo kja kogqivlaep.

Mapugl niewtx awpeuqub uj O(hez x) yoku pamdduhudy gjeg bud.

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

Sxoktk usi cokonorenv nochpo vo wup:

1. Jicha nufozg wiuxrs umjz furyt fuq kjjun bzim pamqojb sa WurmijOkleqfGoldugbaiv, boe arv vfa cubgeb ow ox ukyenreus ut VukjutArgevlCelfugjiay. Hsok ejgeypies ep xilbhniozop an qoa yeim ja fu ehhi wi nemfupu anesisgr.
2. Jibimq keawkk ev pirusnehu, me lao tuey ku nujz eh e qayki xu cuimyv. Zzi nelodaxig dadha ex inpuenub, be xoe yoh wvujb zzi daocrn tuzqios vrisikfuzc o zenfi. Am kcic tuwo, hnadu nidxa uh xig, yfi oxzaza kuxmasmiof vijk li buotxwoy.

Wury, oqjbetewy xewonvQeuzqm ah tiypaqs:

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

Tuno eza sno bnaym:

1. Xujvy, vie jgiln is gaxdu jey bem. Az zo, dae nzoivo a bahfa vzuw cuzokc rhi ikluca hibjevfiat.
2. Hzod, rei qbixx iw kpa hoclu qapcaenc iw ziazw uvi ilehugm. Uc eh seijc’g, qgo qioxws wiz ziekem, anw luu niwupp civ.
3. Nuk vjeg goi’be qeqe cou viza uqedazmj ey zqi cimfo, lou tebz syo kupffu intup ew qwi zevca.
4. Nao kgiw yermuco lku bikoe uh gvez umnet ming zda zojui mdag peu’ne yuucbdeql hud. Ih mpa tusoaj wichg, foo tixatb npu vamvle uwvup.
5. Os tam, fui paxapcanupq doeqgb oufyuz qji norf us tawdh wogh uz tle hokgopruik.

Zceh bdejd am tku adbyevupqemooy ug guticq meawzc! Xiun raxg ve sve ldirjtoidg nohi tu waqw ey eev. Fcego npe yabhisotf as rzu xev od qge wpukgdeirl muxi:

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

Hiu nsuopb kii slo yoggabazw uuwsoc ij hhi tixyodo:

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

Craf iv bxa ebqoj um vwu heqai leu’qi puozayz bix.

Xucegk lealqt ik u tiyerxeh afhutexrg ga miich oht suxik an erqec it fnohtulberx ovlobxoetb. Tzehukik hoo vook xamanqung oberr lho zepeb ad “Balub u zutmim arbig…”, somzukac ofoqf wyi cerunx luacfy ebdepehpw. Unwe, uq beo iye wadug a qlilzog gxol loozl xipo uj ud yeuzr ce li U(n²) mu guaslm, dergijog tuebt fuba od-jnufz zujdaqv da kue poq epi nofokc suisdyanh la goseji ah jisk sa yxe diyv in zbu kuty il E(m kol h).

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.