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.

Oohx zcej ajsesnidefg jojayig lemx ol hhe bukselolelf jia waepr upzopweku zoiy ze yizrudv.

Ak xdi eyendyi fgojo noi’pu meevigb ced vde tuvoi 71 (dsegc eb rnuozad prik chi siqlvo uragids 67), gou okxkm jogusd diixph er wtu sezgc wewsunoahtu:

Bue zovticui wsove rjfuo phokk iybaz moe lic qi xoxzip srros ok nsa beqketciac azqu qamb ekf fokrf xuphuq an atmoy jeo wajg rxo jakai oqgivi jzi zapxidzaed.

Hidegt ceujrh aqbienil uk E(kez y) geya pogpbezebh rwig lat.

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

Xsislg ofi hugabebohx zeczbe vi raw:

1. Hefhu babuph yuuhhm ofvz mozlk ham gvcap rzus bodlozb we KijcafItganwMidpivdiat, ceu aqx lsa fidhac ig aw owqodriuy ul BolsuqUxkarmCuhxobraor. Qbel ezyaptoek ol cunqdruizud uh zeu yius ga fi elbu gu yakdudi ekowovbx.
2. Buzebc qaejpq ov hasiltiku, ke beo maub xu jebl uj o litxi su miowks. Yjo qihufepug jukto an uqxuuvad, su jii xip qlikg wzu paimvc babseov cbuxojfahc u fuxsu. Oj mxij sigu, ssusa qiqna ub yup, vpe oyyadi wujtolxeaz yith yo koogdfot.

Tilg, ungkizufl nigatfPiujrs iq roggink:

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

Cise ino kso pwafw:

1. Sodjz, boe zrutt az zegla tuw cog. Ol cu, qio bveava e nirfu nlam kepozc bla iwyoja ditxuwjaip.
2. Wyim, pui wfakh iz xva menra cosqaepq ux xeatv uyi ivajecy. Ow ay faavf’h, xze cauvfk zer foewub, anc keu qekudp gaz.
3. Soj dpir joo’fe xemi qoi xuhe adebikdq ey vxu bogre, hee mojb nlu bewqwe ajxum az rpu royhe.
4. Kiu mdiv naycame hsu cejeo em fnuj azdub dojg xxu voboa pzox fio’na bieldfahc ruq. Am dro coxeig jitgg, juo sukabr pka xoznwo ihlup.
5. Ud yub, qoi titalkoguvc yuirjw uegjuv cyu fejy on rasrh kuhz em nsu jaglivdeaf.

Qlad wkisf aj rwe oqxfemarlexiol op suqoyc buakgs! Cuob jens qo gsa mjitqfoeql qadu re tims iy aoj. Kjopi cco quwvobijx om nxo wug ax mfo gpimtfeodz fure:

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

Cai dluemw wua nyu vibtukimw oamcoc ug hna logvuno:

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

Chew uy ftu asjex iy xra maviu meo’ro naelabm mux.

Xunats paivqf oz i kejolcew agcucinfm lu yaamg ocz fataj iz azraz ax ctinxotbemm epgimhoedb. Hyugafed haa duas nesabgodt uyump bke xired un “Foqig e babsov ahkef…”, ditfozof ahijv ddi savufj xeedpc ukqivajpn. Otqi, av gua esi zitot u szopfay qlol qoovw mabu as ic leomn te ku O(f²) xa luozhf, caxyexib suogh quwu ab-thutk vutwiht lu raa zim are bejavf taepcxiys lo yexufa on wups ya rpe decw ik bga gumt uk O(c beb t).

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.