I have a sorted array and want to do binary search on it.
So I'm asking if something is already available in Swift library like sort etc.? Or is there a type independend version available?
Of course I could write it by my own, but I like to avoid reinventing the wheel again.
Here's my favorite implementation of binary search. It's useful not only for finding the element but also for finding the insertion index. Details about assumed sorting order (ascending or descending) and behavior with respect to equal elements are controlled by providing a corresponding predicate (e.g. { $0 < x } vs { $0 > x } vs { $0 <= x } vs { $0 >= x }). The comment unambiguously says what exactly does it do.
extension RandomAccessCollection {
/// Finds such index N that predicate is true for all elements up to
/// but not including the index N, and is false for all elements
/// starting with index N.
/// Behavior is undefined if there is no such N.
func binarySearch(predicate: (Element) -> Bool) -> Index {
var low = startIndex
var high = endIndex
while low != high {
let mid = index(low, offsetBy: distance(from: low, to: high)/2)
if predicate(self[mid]) {
low = index(after: mid)
} else {
high = mid
}
}
return low
}
}
Example usage:
(0 ..< 778).binarySearch { $0 < 145 } // 145
if low == high || predicate(self[index(high, offsetBy: -1)]) { return high } before the while loop, to optimize for append operations.
Here's a generic way to use binary search:
func binarySearch<T:Comparable>(_ inputArr:Array<T>, _ searchItem: T) -> Int? {
var lowerIndex = 0
var upperIndex = inputArr.count - 1
while (true) {
let currentIndex = (lowerIndex + upperIndex)/2
if(inputArr[currentIndex] == searchItem) {
return currentIndex
} else if (lowerIndex > upperIndex) {
return nil
} else {
if (inputArr[currentIndex] > searchItem) {
upperIndex = currentIndex - 1
} else {
lowerIndex = currentIndex + 1
}
}
}
}
var myArray = [1,2,3,4,5,6,7,9,10]
if let searchIndex = binarySearch(myArray, 5) {
print("Element found on index: \(searchIndex)")
}
-1 when there is no match. A more Swift like approach would be to return an optional. An alternative good approach would be to return the endIndex when the element is not found.
Comparable protocol
guard !inputArr.isEmpty else { return nil } at the beginning to account for empty array case. Also, I think the else if condition should be lowerIndex >= upperIndexI use an extension on RandomAccessCollection implementing bisectToFirstIndex(where:) and taking a predicate.
test predicate, and returns the index of the first element to pass the test.nil.Collection is empty, it returns nil.let a = [1,2,3,4]
a.map{$0>=3}
// returns [false, false, true, true]
a.bisectToFirstIndex {$0>=3}
// returns 2
You need to ensure test never returns a false for any index after an index it has said true for. This is equivalent to the usual precondition that binary search requires your data to be in order.
Specifically, you must not do a.bisectToFirstIndex {$0==3}. This will not work correctly.
bisectToFirstIndex is useful because it lets you find ranges of stuff in your data. By adjusting the test, you can find the lower and upper limits of "stuff".
Here's some data:
let a = [1,1,1, 2,2,2,2, 3, 4, 5]
We can find the Range of all the 2s like this…
let firstOf2s = a.bisectToFirstIndex { $ 0>= 2 }
let endOf2s = a.bisectToFirstIndex { $0 > 2 }
let rangeOf2s = firstOf2s ..< endOf2s
I use this in an implementation of layoutAttributesForElementsInRect. My UICollectionViewCells are stored sorted vertically in an array. It's easy to write a pair of calls that will find all cells that are within a particular rectangle and exclude any others.
extension RandomAccessCollection {
public func bisectToFirstIndex(where predicate: (Element) throws -> Bool) rethrows -> Index? {
var intervalStart = startIndex
var intervalEnd = endIndex
while intervalStart != intervalEnd {
let intervalLength = distance(from: intervalStart, to: intervalEnd)
guard intervalLength > 1 else {
return try predicate(self[intervalStart]) ? intervalStart : nil
}
let testIndex = index(intervalStart, offsetBy: (intervalLength - 1) / 2)
if try predicate(self[testIndex]) {
intervalEnd = index(after: testIndex)
}
else {
intervalStart = index(after: testIndex)
}
}
return nil
}
}
The implementation here extends RandomAccessCollection and I've updated the code to build with the current Swift version (5 or something).
Binary searches are notoriously hard to correctly code. You really should read that link to find out just how common mistakes in their implementation are, but here is an extract:
When Jon Bentley assigned it as a problem in a course for professional programmers, he found that an astounding ninety percent failed to code a binary search correctly after several hours of working on it, and another study shows that accurate code for it is only found in five out of twenty textbooks. Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contains an error that remained undetected for over twenty years.
Given that last point, here is a test for this code. It passes! The testing isn't exhaustive – so there may certainly still be errors.
final class Collection_BisectTests: XCTestCase {
func test_bisect() {
for length in 0...100 {
let collection = 0 ... length
let targets = -4 ... length + 4
for toFind in targets {
let bisectIndex = collection.bisectToFirstIndex { $0 > toFind }
let expectIndex = collection.firstIndex { $0 > toFind }
XCTAssertEqual(bisectIndex, expectIndex, "Finding \(toFind+1) in 0...\(length)")
}
}
}
}
Indexable: "Important: In most cases, it's best to ignore this protocol and use CollectionType instead, as it has a more complete interface." So as per Vadim's answer I've used extension CollectionType where Index: RandomAccessIndexType. Also I'm wondering if it's worth & possible fool proofing this by ordering (self) before the whileO(n.log(n)) operation. Binary search is a O(log(n)) operation. If you're using a binary search, you probably need that (huge) asymptotic performance difference. If you don't need that difference, you are better off with a completely different algorithm that will handle unordered data.RandomAccessCollection as you suggested 6 years ago :-)extension ArraySlice where Element: Comparable {
func binarySearch(_ value: Element) -> Int? {
guard !isEmpty else { return nil }
let midIndex = (startIndex + endIndex) / 2
if value == self[midIndex] {
return midIndex
} else if value > self[midIndex] {
return self[(midIndex + 1)...].binarySearch(value)
} else {
return self[..<midIndex].binarySearch(value)
}
}
}
extension Array where Element: Comparable {
func binarySearch(_ value: Element) -> Int? {
return self[0...].binarySearch(value)
}
}
This is, in my opinion, very readable and leverages the fact that Swift's ArraySlice is a view on Array and retains the same indexes as the original Array with which it shares the storage so, in absence of mutations (like in this case), it is therefore very efficient.
here is binary search using while syntax
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
}
Here is an implementation for a sorted array of strings.
var arr = ["a", "abc", "aabc", "aabbc", "aaabbbcc", "bacc", "bbcc", "bbbccc", "cb", "cbb", "cbbc", "d" , "defff", "deffz"]
func binarySearch(_ array: [String], value: String) -> String {
var firstIndex = 0
var lastIndex = array.count - 1
var wordToFind = "Not founded"
var count = 0
while firstIndex <= lastIndex {
count += 1
let middleIndex = (firstIndex + lastIndex) / 2
let middleValue = array[middleIndex]
if middleValue == value {
wordToFind = middleValue
return wordToFind
}
if value.localizedCompare(middleValue) == ComparisonResult.orderedDescending {
firstIndex = middleIndex + 1
}
if value.localizedCompare(middleValue) == ComparisonResult.orderedAscending {
print(middleValue)
lastIndex = middleIndex - 1
}
}
return wordToFind
}
//print d
print(binarySearch(arr, value: "d"))
Another implementation: if you want to have your structs or classes searchable without making them Comparable, make them BinarySearchable instead:
public protocol BinarySearchable {
associatedtype C: Comparable
var searchable: C { get }
}
public extension Array where Element: BinarySearchable {
func binarySearch(_ prefix: Element.C) -> Index {
var low = 0
var high = count
while low != high {
let mid = (low + high) / 2
if self[mid].searchable < prefix {
low = mid + 1
} else {
high = mid
}
}
return low
}
}
Example usage for a struct that should be sorted and searched by name:
struct Country: BinraySearchable {
var code: String
var name: String
var searchable: String { name }
}
// Suppose you have a list of countries sorted by `name`, you want to find
// the index of the first country whose name starts with "United", others
// will follow:
let index = listOfCountries.binarySearch("United")
id and you want to sort and search by id, but the array stores entire objects. You define your "searchable" property separately, hence a separate protocol BinarySearchable.And for completeness, here's a entirely pattern matching based implementation:
extension Collection where Element: Comparable {
func binarySearch(for element: Element) -> Index? {
switch index(startIndex, offsetBy: distance(from: startIndex, to: endIndex) / 2) {
case let i where i >= endIndex: return nil
case let i where self[i] == element: return i
case let i where self[i] > element: return self[..<i].binarySearch(for: element)
case let i: return self[index(after: i)..<endIndex].binarySearch(for: element)
}
}
}
The above code should work with any kind of collections, sliced or not sliced, zero offset-ed or non-zero offset-ed.
Here's a better implementation that returns more than one index, if there are more than 1 in the array.
extension Array where Element: Comparable {
/* Array Must be sorted */
func binarySearch(key: Element) -> [Index]? {
return self.binarySearch(key, initialIndex: 0)
}
private func binarySearch(key: Element, initialIndex: Index) -> [Index]? {
guard count > 0 else { return nil }
let midIndex = count / 2
let midElement = self[midIndex]
if key == midElement {
// Found!
let foundIndex = initialIndex + midIndex
var indexes = [foundIndex]
// Check neighbors for same values
// Check Left Side
var leftIndex = midIndex - 1
while leftIndex >= 0 {
//While there is still more items on the left to check
print(leftIndex)
if self[leftIndex] == key {
//If the items on the left is still matching key
indexes.append(leftIndex + initialIndex)
leftIndex--
} else {
// The item on the left is not identical to key
break
}
}
// Check Right side
var rightIndex = midIndex + 1
while rightIndex < count {
//While there is still more items on the left to check
if self[rightIndex] == key {
//If the items on the left is still matching key
indexes.append(rightIndex + initialIndex)
rightIndex++
} else {
// The item on the left is not identical to key
break
}
}
return indexes.sort{ return $0 < $1 }
}
if count == 1 {
guard let first = first else { return nil }
if first == key {
return [initialIndex]
}
return nil
}
if key < midElement {
return Array(self[0..<midIndex]).binarySearch(key, initialIndex: initialIndex + 0)
}
if key > midElement {
return Array(self[midIndex..<count]).binarySearch(key, initialIndex: initialIndex + midIndex)
}
return nil
}
}
By recursive binary search,
func binarySearch(data : [Int],search: Int,high : Int,low:Int) -> Int? {
if (low > high)
{
return nil
}
let mid = low + (low + high)/2
if (data[mid] == search) {
return mid
}
else if (search < data[mid]){
return binarySearch(data: data, search: search, high: high-1, low: low)
}else {
return binarySearch(data: data, search: search, high: high, low: low+1)
}
}
Input : let arry = Array(0...5) // [0,1,2,3,4,5]
print(binarySearch(data: arry, search: 0, high: arry.count-1, low: 0))
Here is how you create a binary search function in swift 5, in this example I assume that the item you are looking for is guaranteed to be in the list, however if your item is not guaranteed to be in the list then you can run this code to check first:
yourList.contains(yourItem) //will return true or false
Here is the binary search function:
override func viewDidLoad() {
super.viewDidLoad()
print(binarySearch(list: [1, 2, 4, 5, 6], num: 6)) //returns 4
}
func binarySearch(list: [Int], num: Int) -> Int //returns index of num
{
var firstIndex = 0
var lastIndex = list.count - 1
var middleIndex = (firstIndex + lastIndex) / 2
var middleValue = list[middleIndex]
while true //loop until we find the item we are looking for
{
middleIndex = (firstIndex + lastIndex) / 2 //getting the list's middle index
middleValue = list[middleIndex]
if middleValue > num
{
lastIndex = middleIndex - 1 //get the left side of the remaining list
}
else if middleValue < num
{
firstIndex = middleIndex + 1 //get the right side of the remaining list
}
else if middleValue == num
{
break //found the correct value so we can break out of the loop
}
}
return middleIndex
}
I have made a youtube video explaining this here
Simple solution in Swift 5:
func binarySerach(list: [Int], item: Int) -> Int? {
var low = 0
var high = list.count - 1
while low <= high {
let mid = (low + high) / 2
let guess = list[mid]
if guess == item {
return mid
} else if guess > item {
high = mid - 1
} else {
low = mid + 1
}
}
return nil
}
let myList = [1,3,4,7,9]
print(binarySerach(list: myList, item: 9))
//Optional(4)
import Foundation
extension RandomAccessCollection where Element: Comparable {
private func binarySearchIteration(forIndexOf value: Element, in range: Range<Index>? = nil,
valueDetected: ((Index, _ in: Range<Index>) -> Index?)) -> Index? {
let range = range ?? startIndex..<endIndex
guard range.lowerBound < range.upperBound else { return nil }
let size = distance(from: range.lowerBound, to: range.upperBound)
let middle = index(range.lowerBound, offsetBy: size / 2)
switch self[middle] {
case value: return valueDetected(middle, range) ?? middle
case ..<value: return binarySearch(forIndexOf: value, in: index(after: middle)..<range.upperBound)
default: return binarySearch(forIndexOf: value, in: range.lowerBound..<middle)
}
}
func binarySearch(forIndexOf value: Element, in range: Range<Index>? = nil) -> Index? {
binarySearchIteration(forIndexOf: value, in: range) { currentIndex, _ in currentIndex }
}
func binarySearch(forFirstIndexOf value: Element, in range: Range<Index>? = nil) -> Index? {
binarySearchIteration(forIndexOf: value, in: range) { currentIndex, range in
binarySearch(forFirstIndexOf: value, in: range.lowerBound..<currentIndex)
}
}
func binarySearch(forLastIndexOf value: Element, in range: Range<Index>? = nil) -> Index? {
binarySearchIteration(forIndexOf: value, in: range) { currentIndex, range in
binarySearch(forFirstIndexOf: value, in: index(after: currentIndex)..<range.upperBound)
}
}
func binarySearch(forIndicesRangeOf value: Element, in range: Range<Index>? = nil) -> Range<Index>? {
let range = range ?? startIndex..<endIndex
guard range.lowerBound < range.upperBound else { return nil }
guard let currentIndex = binarySearchIteration(forIndexOf: value, in: range, valueDetected: { index, _ in index
}) else { return nil }
let firstIndex = binarySearch(forFirstIndexOf: value, in: range.lowerBound ..< index(after: currentIndex)) ?? currentIndex
let lastIndex = binarySearch(forFirstIndexOf: value, in: index(after: currentIndex) ..< range.upperBound) ?? currentIndex
return firstIndex..<index(after: lastIndex)
}
}
//let array = ["one", "two", "three", "three", "three", "three", "three", "four", "five", "five"]
//let value = "three"
let array = [1, 2, 3, 3, 3, 3, 3, 4, 5, 5]
let value = 3
print(array.binarySearch(forFirstIndexOf: value))
print(array.binarySearch(forLastIndexOf: value))
print(array.binarySearch(forIndicesRangeOf: value))
protocol _BinarySearchTestable: class where Collection: RandomAccessCollection, Collection.Element: Comparable {
associatedtype Collection
var array: Collection! { get set }
var elementToSearch: Collection.Element! { get set }
func testFindFirstIndexOfValueInCollection()
func testFindLastIndexOfValueInCollection()
func testFindIndicesRangeOfValueInCollection()
}
extension _BinarySearchTestable where Self: XCTest {
typealias Element = Collection.Element
typealias Index = Collection.Index
func _testFindFirstIndexOfValueInCollection() {
_testfindFirstIndex(comparableArray: array, testableArray: array)
}
func _testFindLastIndexOfValueInCollection() {
let index1 = array.lastIndex(of: elementToSearch)
let index2 = array.binarySearch(forLastIndexOf: elementToSearch)
_testElementsAreEqual(indexInComparableArray: index1, comparableArray: array,
indexInTestableArray: index2, testableArray: array)
}
func _testFindIndicesRangeOfValueInCollection() {
var range1: Range<Index>?
if let firstIndex = array.firstIndex(of: elementToSearch),
let lastIndex = array.lastIndex(of: elementToSearch) {
range1 = firstIndex ..< array.index(after: lastIndex)
}
let range2 = array.binarySearch(forIndicesRangeOf: elementToSearch)
XCTAssertEqual(range1, range2)
}
private func _testElementsAreEqual(indexInComparableArray: Index?, comparableArray: Collection,
indexInTestableArray: Index?, testableArray: Collection) {
XCTAssertEqual(indexInComparableArray, indexInTestableArray)
var valueInComparableArray: Element?
if let index = indexInComparableArray { valueInComparableArray = comparableArray[index] }
var valueInTestableArray: Element?
if let index = indexInComparableArray { valueInTestableArray = testableArray[index] }
XCTAssertEqual(valueInComparableArray, valueInTestableArray)
}
private func _testfindFirstIndex(comparableArray: Collection, testableArray: Collection) {
let index1 = comparableArray.firstIndex(of: elementToSearch)
let index2 = testableArray.binarySearch(forFirstIndexOf: elementToSearch)
_testElementsAreEqual(indexInComparableArray: index1, comparableArray: comparableArray,
indexInTestableArray: index2, testableArray: testableArray)
}
}
class TestsInEmptyArray: XCTestCase, _BinarySearchTestable {
var array: [String]!
var elementToSearch: String!
override func setUp() {
array = []
elementToSearch = "value"
}
func testFindFirstIndexOfValueInCollection() { _testFindFirstIndexOfValueInCollection() }
func testFindLastIndexOfValueInCollection() { _testFindLastIndexOfValueInCollection() }
func testFindIndicesRangeOfValueInCollection() { _testFindIndicesRangeOfValueInCollection() }
}
class TestsInArray: XCTestCase, _BinarySearchTestable {
var array: [Int]!
var elementToSearch: Int!
override func setUp() {
array = [1, 2, 3, 3, 3, 3, 3, 4, 5, 5]
elementToSearch = 3
}
func testFindFirstIndexOfValueInCollection() { _testFindFirstIndexOfValueInCollection() }
func testFindLastIndexOfValueInCollection() { _testFindLastIndexOfValueInCollection() }
func testFindIndicesRangeOfValueInCollection() { _testFindIndicesRangeOfValueInCollection() }
}
class TestsInArrayWithOneElement: XCTestCase, _BinarySearchTestable {
var array: [Date]!
var elementToSearch: Date!
override func setUp() {
let date = Date()
array = [date]
elementToSearch = date
}
func testFindFirstIndexOfValueInCollection() { _testFindFirstIndexOfValueInCollection() }
func testFindLastIndexOfValueInCollection() { _testFindLastIndexOfValueInCollection() }
func testFindIndicesRangeOfValueInCollection() { _testFindIndicesRangeOfValueInCollection() }
}
Arrays.binarySearch()was broken until version 6.0 of the SDK. As a plug for my own answer, it includes tests.