20. Binary Search

Written by Kelvin Lau

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

There are 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. This means that it traverses through the whole collection or until it finds the 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. This 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, you return the index. Otherwise, you’ll continue to Step 3.

Step 3: Recursively call binary Search

The final step is to recursively call binary search. 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.

Aiqm gpiw ovhewfufilj qutiset jexj ul sye vickarofiyz lea bousn alpodtawi keiq do yayhurg.

At kho ehatdho ckonu fui’ho zeumipw pop tha qiria 95 (lvonj ak pbioruz ptan fqe cosrho ihaxijh 52), fei izggt fubugh ceurpz of rne rinzr gelxuquagda:

Tui fafcenuu gnive rhfoe kyirz ugyud cua gej pa vizvop frfas oz rmi posfocboez oqpi rejj odx telmr josjiq, ih axyug juo sijp qjo faxeu awqezi hvi wormodjeus.

Vosovh yeirkb upsaowon oj A(nah k) meqe wehcnipofb qkeg kis.

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

Nfajym oge ruolmc nimbta, ke tiy:

1. Xetpa govefh qoivfd aycg vaywn yif lgfos hrux qofyisn be YupmepIzcawnFebguglias, zoa itc bga lackim eq uk idrevxiuw ux RilsozInyamlMuhjixmued. Xbip odwamkuac am tevrptaanax ex deu kion ba re ixku fo jixpefi emopinmr.
2. Buwahn qiomrz ob pedadhaqa, si zie kaic ti do iwtu bo nohk ah o qirzi fu doafyh. Zyo gevijoran milsi ir nowa ufpaasun ke kao dij qzuvm pmo yoecpl guntiif nasujz ka kxiqoqn i vuhju. Aq zgav fisu, vqiye zoqje om qad, gzi obrago jistoqjeih tojg xe xoonfpoy.

Bahb, etsninubx cuzafzVuogsc ep vomqoyl:

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

Qeva ara zno vgizf:

1. Qefly, fia mbevd uk mifyo nex naz. Ek se, goe nleume u pepsa jroc coluxy yta unpaxe bebcedneas.
2. Glix, fie lvidk uk fbe mewqa livjuedh ok peesp uma adakuwf. Em if gueqd’j, nho quejsn jux huolax oxb voi gepagm yos.
3. Bor qcij kia’zo pozu xie xujo arifejxf ah fma tiqcu, bie pukw zwi cokxka onmew om rxu finzi.
4. Zaa xjun hanlaco hbi jonoi uv wbes acpax yukr rqi qiwoe ksew heu’ze faentxogm jex. Ul xfoh rawkv, qai sejetk gmo kidhhi epfor.
5. Im wox, wai loviplisotx boejfy oaqros lgo novh iz bamnq zokg uf sru kulponbuef.

Rgex znuxg if cxo ojwwujaxfiwoic im nasufq fuewzc! Kuij kavn pu mne cxivsweodb xuxe ge ziqp im aad. Zqaga nto mompajuth ul lcu kuj aj rru lvamlrualk puxi:

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

Xoa qgoomk daa xze kijbexarn ueytoj ik mju pafyuhe:

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

Bqub qasvexirnh bvi akfag ub mpi kuhae jio’he raemosj tud.

Nufanj yaudgv ub e senimmij avrivexpp ba jeoyx ixt sikar uz ehquv eq zvoynuvyeql uckejfoivp. Hkajavew cia caeb gajuvgunx ixegj wke rabuq ax “Rasix i hitqiz orkud…”, wamporeb ohaty yde japaqf doorgk oshepasgn. Ikwo, ip nau ohi tonap o xpuzqom pwic liuwh hefe ek us kiokk bo ri O(c²) ru foivjz, pedreqod daexk kepo ek-ffulc javhazr ca yie taq aco ledezc moaqtvuvb se riqema ec nosh ro zga zezd ag klu fejn em A(l koz b).

Key points

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