This article is a translation of Swift Algorithm Club.
Swift Algorithm Club is an open source project produced by Raywenderlich.com to realize algorithms and data structures by Swift. Currently, there are 18000+⭐️ on GitHub. I have made a brief statistics, and there are about 100 algorithms and data structures. It’s basically a good resource for iOSer learning algorithms and data structures.
🐙andyRon/ swift-algorithm-club-CN is my project of learning and translating for Swift Algorithm Club. Due to the limited capacity, if you find any errors or improper translation, please correct them. Welcome to Pull Request. Also welcome interested, have time partners to participate in translation and learning 🤓. Of course, we welcome ⭐️, 🤩🤩 ️ ⭐ ⭐.
A translation of this article and the code can be found at 🐙swift-algorithm-club-cn/Binary Search
Target: Quickly find an element in an array.
Suppose you have an array of numbers and you want to determine if a particular number is in the array and, if so, get the index of that number.
For the above case, Swift’s indexOf() function is sufficient:
let numbers = [11.59.3.2.53.17.31.7.19.67.47.13.37.61.29.43.5.41.23]
numbers.indexOf(43) // returns 15
Copy the codeThe built-in indexOf() function performs a linear search. The code looks like this:
func linearSearch<T: Equatable>(_ a: [T], _ key: T) -> Int? {
for i in 0 ..< a.count {
if a[i] == key {
return i
}
}
return nil
}
Copy the codeUse as follows:
linearSearch(numbers, 43) // returns 15
Copy the codeWhat seems to be the problem? LinearSearch () walks through the array from scratch until you find the element you are looking for. In the worst case, the value is not in the array, so the previous traversal is useless.
On average, a linear search algorithm looks at half of the values in the array. If your array is large enough, this will get very slow!
Divide and conquer
The classic way to speed things up is to use binary search. The trick is to split the array in half until you find the value.
For an array of size N, the performance is not O(n) of linear search, but only O(log n). In other words, a binary search of an array of 1,000,000 elements requires only about 20 steps to find what to look for, because log_2 (1,000,000) = 19.9. For an array of a billion elements, it takes only 30 steps. (However, when was the last time you used an array of billions of items?)
That sounds great, but there is a drawback to binary search: the array must be sorted. In practice, this is usually not a problem.
Here’s how binary search works:
- Divide the array in half and determine what you are looking for (calledThe search buttonIs it in the left half or the right half.
- How do you determineThe search buttonWhat is the half of the sigma bond? That’s why you sort the array in the first place, so you can do a simple one
<or>Comparison. - ifThe search buttonIn the left half, repeat the process there: divide the left half into two smaller sections and viewThe search buttonWhere is it located? (Again, do the same for the right half.)
- Repeat until foundThe search button. If you can’t split the array any further, you must unfortunately conclude thatThe search buttonNot in the array.
Now you know why it’s called a “binary” search: at each step it splits the array in half. Divide and conquer quickly Narrows the search key.
code
This is a recursive implementation of binary search in Swift:
func binarySearch<T: Comparable>(_ a: [T], key: T, range: Range<Int>) -> Int? {
if range.lowerBound >= range.upperBound {
// If we get here, then the search key is not present in the array.
return nil
} else {
// Calculate where to split the array.
let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
// Is the search key in the left half?
if a[midIndex] > key {
returnbinarySearch(a, key: key, range: range.lowerBound .. < midIndex)// Is the search key in the right half?
} else if a[midIndex] < key {
return binarySearch(a, key: key, range: midIndex + 1 ..< range.upperBound)
// If we get here, then we've found the search key!
} else {
return midIndex
}
}
}
Copy the codeTry copying the code to playground and doing the following:
let numbers = [2.3.5.7.11.13.17.19.23.29.31.37.41.43.47.53.59.61.67]
binarySearch(numbers, key: 43, range: 0 ..< numbers.count) // gives 13
Copy the codeNotice that the numbers array is sorted. Otherwise the binary search algorithm won’t work!
Binary search searches by splitting an array in half, but we don’t actually create two new arrays. We use SwiftRange objects to track these splits. Initially, this range covers the entire array, 0.. “The Numbers. The count. As we split the array, the range gets smaller and smaller.
Note: One thing to note is that range.upperBound always points to the element after the last element. In this case, the range is 0.. <19, because there are 19 numbers in the array, range.lowerBound = 0 and range.upperBound = 19. But in our array, the last element is in index 18 instead of 19, because we’re counting from 0. Keep this in mind when working with scopes: upperBound is always one more index than the last element.
Step by step to execute the example
It might be useful to see how the algorithm works in detail.
The array in the above example consists of 19 digits, sorted as follows:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67]Copy the codeWe’re trying to determine if the number 43 is in this array.
To split the array in half, we need to know the index of the intermediate object. This is determined by this line of code:
let midIndex = range.lowerBound + (range.upperBound - range.lowerBound) / 2
Copy the codeOriginally, the ranges had lowerBound = 0 and upperBound = 19. On closer inspection, we see that midIndex is 0 + (19-0) /2 = 19/2 = 9. It’s actually 9.5, but since we’re using integers, the answer is rounded down.
In the figure below, * represents the middle item. As you can see, there are the same number of items on each side, so we will split them in the middle.
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67] *Copy the codeBinary search will determine which half of the relevant code to use is:
if a[midIndex] > key {
// use left half
} else if a[midIndex] < key {
// use right half
} else {
return midIndex
}
Copy the codeIn this case, a[midIndex] = 29. This is smaller than the value of the search key, so we can conclude that the search key never appears in the left half of the array. After all, the left half only contains numbers less than 29. Therefore, the search key must be in the right half (or not in the array at all).
Now we can simply repeat binary search with array spacing from midIndex + 1 to range.upperbound:
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
Copy the codeSince we no longer need to focus on the left half of the array, I’ve labeled it with an X. From now on, we’ll just look at the right half, starting with the array index 10.
We compute the index of the new intermediate element: midIndex = 10 + (19-10) / 2 = 14, and then split the array down the middle.
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43, 47, 53, 59, 61, 67 ]
*
Copy the codeAs you can see, a [14] is the middle element in the right half of the array.
Is the search key greater than or less than a [14]? Small, because 43 is less than 47. This time we take the left half and ignore the larger numbers on the right:
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ]
Copy the codeThe new midIndex is as follows:
[ x, x, x, x, x, x, x, x, x, x | 31, 37, 41, 43 | x, x, x, x, x ]
*
Copy the codeThe search key is greater than 37, so continue to the right:
[ x, x, x, x, x, x, x, x, x, x | x, x | 41, 43 | x, x, x, x, x ]
*
Copy the codeAgain, the search key is larger, so split again and take the right:
[ x, x, x, x, x, x, x, x, x, x | x, x | x | 43 | x, x, x, x, x ]
*
Copy the codeNow we’re done. The search key is equal to the array element we are looking at, so we finally find what we are searching for: the number 43 is in index 13.
This may seem like a lot of work, but it actually takes only four steps to find the search key in the array, because log_2 (19) = 4.23. By linear search, it will take 14 steps.
What happens if we want to search 42 instead of 43? In this case, finally we can’t split the array any further. Range.upperbound becomes less than range.lowerbound. This tells the algorithm that the search key is not in the array, and it returns nil.
Note: Many binary searches evaluate midIndex = (lowerBound + upperBound) / 2. This contains a subtle bug that can occur in very large arrays, because lowerBound + upperBound may overflow the maximum number an integer can hold. This is unlikely to happen on 64-bit cpus, but it definitely can happen on 32-bit machines.
Iteration and recursion
Binary search is recursive in nature, because you apply the same logic to smaller and smaller subarrays over and over again. However, this does not mean that you must implement binarySearch() as a recursive function. It is often more efficient to convert a recursive algorithm to an iterative version, using simple loops rather than lots of recursive function calls.
This is an iterative implementation of binary search in Swift:
func binarySearch<T: Comparable>(_ a: [T], key: T) -> Int? {
var lowerBound = 0
var upperBound = a.count
while lowerBound < upperBound {
let midIndex = lowerBound + (upperBound - lowerBound) / 2
if a[midIndex] == key {
return midIndex
} else if a[midIndex] < key {
lowerBound = midIndex + 1
} else {
upperBound = midIndex
}
}
return nil
}
Copy the codeAs you can see, the code is very similar to the recursive version. The main difference is the use of a while loop.
Using iteration:
let numbers = [2.3.5.7.11.13.17.19.23.29.31.37.41.43.47.53.59.61.67]
binarySearch(numbers, key: 43) // gives 13
Copy the codeThe end of the
Is it a problem that arrays have to be sorted first? Sorting takes time — a combination of binary search and sorting can be slower than a simple linear search. But in cases where you sort only once and then search multiple times, binary search works.
Binary search wikipedia
Translated by Andy Ron proofread by Andy Ron