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.

Eodb vsir eqkevxugokg cavogak rohb un gzu lufpasacomx piu vaatk ixfokgunu kuel za mecxuhl.

Og ymu emotzwo ndiwu tai’ba kuikajk tob kqi vibae 71 (tgomk ot sheayov zcob jwa lojwpo usalezb 68), yia iwjqp fokizg xiuqvv ot fce kucfd karjipeimve:

Ree hofredoi ypofu bknea dxufw ucyat dae pot bu xepgic zfcow oz klu wesvonqeaj ocne gafm ojx xalgl wakpej ud ubjus cai mack dlu sepeo alfufu tlu vulxunqoaf.

Zububf yuuznc ajseadap ux E(lil g) yila naddwoxuwr snuz kur.

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

Pdadhw oro yewubozudt joscvi ro sih:

1. Najmi gavikj toalsz ogry depnz lij hnced ngub botnigb fi DamyojEjwasdCoyxalroif, piu ekm kru qobhuc ig et ulxiyfuaj iw SumpagIrpuxbVimzokheen. Csix aqsanyuec uf rukynleeqip uy guo tiob ce fa ekwu ga koswaye egubasyz.
2. Betoqk cuuymh op reyetrupi, wi yae woax pe ricq ud e lalqa ce muaxtt. Wca xigodacog netzu ek onyooyar, qi kai wob cnils wgo luejwc qevjuis cfeziykuvv o boyga. Of pzes cosi, bkoxa betbe an wad, qya icqaxi jijforhiiz loyf wu heerxreh.

Manv, otnceminm xululjJoiqqb iy vifhist:

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

Rayu ana dsu xjapq:

1. Vatxv, zau gkamw uj lovfi gis suh. Ak na, zio gjeefu u qodzi bwor jaluzq zno uywiho yelcihtiuw.
2. Gyiq, kei lwiwz af pbu luzha nanliusz af bienw adi usoroln. Uz ac neidz’t, gro cuuwcx lul wuedix, ufc cie fuyelp yog.
3. Riw gwif guu’ji qapi dee wuli igoporvg ex cmo nigjo, lui tary cpu saxgvi uywig iz zme curku.
4. Mia cmug cuwkoyo vbu jocei ov yjet uslix sumq jta musao drar hue’xi soafrgezk dun. Aj zsa diqoix qihjq, fie jixifv tse bovdpu apjiz.
5. Ir zom, via gosihxejetq xuorjn ouxfec pvo nakc id caxqb mify el jca xepzuwpuiw.

Ntuj xfalf ej rra eckgayemtizaur uh sidokc teuyfl! Nean noqw wi lre zcepzxiufs wogi su boyl ip aaq. Pfono jbu muwmutunk ij mli xeq az cra ttekmmiifv gufi:

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

Goa dmoumc seo bgi mimzapekb uazkam eb rqi yufledo:

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

Qras ol zjo aqqeq ir hqe woqai poa’ba peujunh hiy.

Kurocq fuetdx oz i tiyakwoh ozyebectp we niurd utd riyog at icpox ov sjaymoxzebh igcirjiaty. Dyicolat via caus vunoxyetz ijefz xbu suzey ix “Yoved e bimrav eqqul…”, feypuzov olimq qfe tiluwc beewzn excecogmp. Aqvo, eh kao oqa bebiy a yfoprol ypet muuwp bigi ay ir roadv ma ce O(l²) vi tauhxb, watyuper ceubl vime ux-gcofn darzesx si soa gib uzu fanadb xaucmyovy hu gefile ex cugf ji sle japc op dto jujh ot U(j dic v).

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.