Swift: Binary search for standard array?

Question

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.

Solution 1

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

Solution 2

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

Solution 3

I use an extension on Indexable implementing indexOfFirstObjectPassingTest.

• It takes a test predicate, and returns the index of the first element to pass the test.
• If there is no such index, then it returns endIndex of the Indexable.
• If the Indexable is empty, you get the endIndex.

Example

let a = [1,2,3,4]

a.map{$0>=3}
// returns [false, false, true, true]

a.indexOfFirstObjectPassingTest {$0>=3}
// returns 2

Important

You need to ensure test never returns in 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.indexOfFirstObjectPassingTest {$0==3}. This will not work correctly.

Why?

indexOfFirstObjectPassingTest 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.indexOfFirstObjectPassingTest({$0>=2})
let endOf2s = a.indexOfFirstObjectPassingTest({$0>2})
let rangeOf2s = firstOf2s..<endOf2s

• If there are no 2s in the data, we'll get back an empty range, and we don't need any special handling.
• Provided there are 2s, we'll find all of them.

As an example, 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.

Code

extension Indexable {
  func indexOfFirstObjectPassingTest( test: (Self._Element -> Bool) ) -> Self.Index {
    var searchRange = startIndex..<endIndex

    while searchRange.count > 0 {
      let testIndex: Index = searchRange.startIndex.advancedBy((searchRange.count-1) / 2)
      let passesTest: Bool = test(self[testIndex])

      if(searchRange.count == 1) {
        return passesTest ? searchRange.startIndex : endIndex
      }

      if(passesTest) {
        searchRange.endIndex = testIndex.advancedBy(1)
      }
      else {
        searchRange.startIndex = testIndex.advancedBy(1)
      }
    }

    return endIndex
  }
}

Disclaimer & Caution

I have about 6 years of iOS experience, 10 of Objective C, and >18 programming generally…

…But I'm on day 3 of Swift :-)

1. I've used an extension on the Indexable protocol. This might be stupid approach – feedback welcomed.
2. 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 are test for this code. They pass. They are unlikely to be exhaustive – so there may certainly still be errors. The tests are not guaranteed to actually be correct! There are no tests for the tests.

Tests

class BinarySearchTest: XCTestCase {

  func testCantFind() {
    XCTAssertEqual([].indexOfFirstObjectPassingTest {(_: Int) -> Bool in false}, 0)
    XCTAssertEqual([1].indexOfFirstObjectPassingTest {(_: Int) -> Bool in false}, 1)
    XCTAssertEqual([1,2].indexOfFirstObjectPassingTest {(_: Int) -> Bool in false}, 2)
    XCTAssertEqual([1,2,3].indexOfFirstObjectPassingTest {(_: Int) -> Bool in false}, 3)
    XCTAssertEqual([1,2,3,4].indexOfFirstObjectPassingTest {(_: Int) -> Bool in false}, 4)
  }

  func testAlwaysFirst() {
    XCTAssertEqual([].indexOfFirstObjectPassingTest {(_: Int) -> Bool in true}, 0)
    XCTAssertEqual([1].indexOfFirstObjectPassingTest {(_: Int) -> Bool in true}, 0)
    XCTAssertEqual([1,2].indexOfFirstObjectPassingTest {(_: Int) -> Bool in true}, 0)
    XCTAssertEqual([1,2,3].indexOfFirstObjectPassingTest {(_: Int) -> Bool in true}, 0)
    XCTAssertEqual([1,2,3,4].indexOfFirstObjectPassingTest {(_: Int) -> Bool in true}, 0)
  }

  func testFirstMatch() {
    XCTAssertEqual([1].indexOfFirstObjectPassingTest {1<=$0}, 0)
    XCTAssertEqual([0,1].indexOfFirstObjectPassingTest {1<=$0}, 1)
    XCTAssertEqual([1,2].indexOfFirstObjectPassingTest {1<=$0}, 0)
    XCTAssertEqual([0,1,2].indexOfFirstObjectPassingTest {1<=$0}, 1)
  }

  func testLots() {
    let a = Array(0..<1000)
    for i in a.indices {
      XCTAssertEqual(a.indexOfFirstObjectPassingTest({Int(i)<=$0}), i)
    }
  }
}

Solution 4

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.

Solution 5

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
}

View more solutions

Comments

[Vadim Yelagin]

Btw when Index is Int and startIndex is zero the result is the number of elements for which the predicate is true.

[AJP]

Thanks very much for the detailed answer and explanation(s). I read in the swift 2.x docs for 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 while

[Benjohn]

Hi @ajp, thanks for the thoughts. 1. I don't know the swift standard libraries well (still!), but in general, I would use the minimum interface that supports the functionality required. 2. I understand your concern but I would advise against the sort before hand. Sorting is (in most cases) an O(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.

[AJP]

Thanks @Benjohn, understood, nice logic.

[Martin R]

A Swift 3 version was posted at stackoverflow.com/questions/40226479/….

[Vadim Yelagin]

Thanks, Martin! I've updated the answer with your Swift 3 converted code.

[jazzgil]

Add if low == high || predicate(self[index(high, offsetBy: -1)]) { return high } before the while loop, to optimize for append operations.

[Benjohn]

I'm going to plug a link to my answer because: 1 – it has some tests. 2 – it defines what happens if there is no element matching the block. This is extremely useful because you can use it to get ranges of elements out, and you can also gracefully detect when the input does not contain the element that you are searching for.

[Benjohn]

This would be greatly improved by not returning -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.

[Daniel Krom]

@Benjohn Totally agreed about the optional, answer is 2 years old and it's time to edit it :)

[Larry Lo]

it is also possible to be applied on string ?

[Larry Lo]

How about string version ?

[Benjohn]

@RajuyourPepe The code is generic, so it'll work on any sorted collection, including sorted strings. Unless you mean binary searching within a string? That would need characters to be sorted, which you could also do, and it might be useful.

[taylor swift]

this should be an extension on RandomAccessCollection, not Collection. This extension can only guarantee O(n log n) complexity.

[Dan Rosenstark]

@taylorswift why not O(logn) which seems to be the normal thing for binary search? Thanks

[taylor swift]

@DanRosenstark dereferencing a Collection index is only guaranteed to be O(n), not O(1)

[Vadim Yelagin]

Subscripting into Collection is always O(1), but offsetting index by K is O(K). Thus overall complexity for this extension on Collection is O(N) (because N/2 + N/4 + N/8 + ... + 1). Complexity for RandomAccessCollection is O(logN) because offsetting is O(1).

[Dan Rosenstark]

VadimYelagin are you and @taylorswift disagreeing on this or agreeing? Sorry to drag this out, thanks everybody

[Vadim Yelagin]

@DanRosenstark taylorswift is absolutely right that this algorithm guarantees O(logN) complexity only for RandomAccessCollection, not for an arbitrary Collection. However the specific reason for why that is the case was not exactly correct, so I felt I needed to clarify it to avoid further confusion in the comments.

[Dan Rosenstark]

Got it and your comment above makes sense. I guess it’s not just adding two numbers together!

[Khuong]

@RajuyourPepe for class that conform to Comparable protocol

[Admin]

@VadimYelagin - I'm not sure I understand the example usage correctly - does (0 ..< 778).binarySearch { $0 < 145 } ask binary search to return all the values between 0 and 778 that are less than 145? Another question I have - can we only check for ranges with this implementation of binary search or could we also do something such as $0 == 145 instead of $0 < 145?

[Coconuts]

you should add 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 >= upperIndex

[Era]

The BinarySearchable type is pointless, you could just directly use Comparable instead.

[mojuba]

@ErikAigner not if the search key is not the object itself. Say you have an object with 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.

[Era]

That way you could make one object only searchable by a single property, because you can only extend it once. If you use Comparable directly you can wrap your stored object in a struct that implements the comparison behavior you want.

[mojuba]

@ErikAigner I know but making an object Comparable by just one property may be undesirable and even dangerous - think of accidental comparisons. Binray search is a very specific functionality and I prefer limiting this type of comparisons to it.

[Justin Meiners]

@taylorswift binary search on linked list can be a perfectly good thing to do. C++ requires the equivalent of collection.

[Robert Dodier]

I'm late to this party, but anyway. It seems like a deficiency that "Behavior is undefined if there is no such N." That said, if all the predicate is false for all elements, or true for all elements, it seems like the correct result (according to the description) is startIndex or endIndex, respectively.

[Vadim Yelagin]

@RobertDodier Undefined (or at least useless) behavior on unsorted arrays is an inherent property of binary search algorithm.