Last active
December 29, 2015 00:18
-
-
Save alejandro-isaza/1f49f9100434f6c6cd1e to your computer and use it in GitHub Desktop.
Binary search in Swift
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public extension CollectionType where Index == Int, Generator.Element: Comparable { | |
/// Perform a binary search for an element. | |
/// | |
/// - precondition: The elements in the collection are sorted. | |
/// - complexity: O(log₂(n)) | |
/// | |
/// - returns: The index of the element or `nil` if the element was not found. | |
public func binarySearch(element: Generator.Element) -> Index? { | |
var low = startIndex | |
var high = endIndex | |
while low < high { | |
let currentIndex = (low + high) / 2 | |
let currentElement = self[currentIndex] | |
if currentElement == element { | |
return currentIndex | |
} | |
if currentElement > element { | |
high = currentIndex | |
} else { | |
low = currentIndex + 1 | |
} | |
} | |
return nil | |
} | |
/// Return the first element that is not less than `element` | |
/// | |
/// - precondition: The elements in the collection are sorted. | |
/// - complexity: O(log₂(n)) | |
/// | |
/// - returns: An index to the lower bound of the element. | |
public func lowerBound(element: Generator.Element) -> Index { | |
var low = startIndex | |
var high = endIndex | |
while low < high { | |
let currentIndex = (low + high) / 2 | |
let currentElement = self[currentIndex] | |
if currentElement < element { | |
low = currentIndex + 1 | |
} else { | |
high = currentIndex | |
} | |
} | |
return low | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import XCTest | |
class BinarySearchTests: XCTestCase { | |
func testBinarySearch() { | |
let case1: [Int] = [1, 1, 1, 1] | |
XCTAssertNil(case1.binarySearch(0)) | |
XCTAssertNil(case1.binarySearch(2)) | |
XCTAssertNil(case1.binarySearch(3)) | |
XCTAssertNil(case1.binarySearch(4)) | |
XCTAssertNotNil(case1.binarySearch(1)) | |
let case2: [Int] = [1, 3, 3, 5] | |
XCTAssertNil(case2.binarySearch(0)) | |
XCTAssertNil(case2.binarySearch(2)) | |
XCTAssertNil(case2.binarySearch(4)) | |
XCTAssertNotNil(case2.binarySearch(3)) | |
XCTAssertEqual(case2.binarySearch(1), 0) | |
XCTAssertEqual(case2.binarySearch(5), 3) | |
let case3: [Int] = [1, 3, 5, 7] | |
XCTAssertNil(case3.binarySearch(0)) | |
XCTAssertNil(case3.binarySearch(2)) | |
XCTAssertNil(case3.binarySearch(4)) | |
XCTAssertEqual(case3.binarySearch(1), 0) | |
XCTAssertEqual(case3.binarySearch(3), 1) | |
XCTAssertEqual(case3.binarySearch(5), 2) | |
} | |
func testLowerBound() { | |
let case1: [Int] = [1, 1, 1, 1] | |
XCTAssertEqual(case1.lowerBound(0), 0) | |
XCTAssertEqual(case1.lowerBound(1), 0) | |
XCTAssertEqual(case1.lowerBound(2), 4) | |
let case2: [Int] = [1, 3, 3, 5] | |
XCTAssertEqual(case2.lowerBound(0), 0) | |
XCTAssertEqual(case2.lowerBound(1), 0) | |
XCTAssertEqual(case2.lowerBound(2), 1) | |
XCTAssertEqual(case2.lowerBound(3), 1) | |
XCTAssertEqual(case2.lowerBound(4), 3) | |
XCTAssertEqual(case2.lowerBound(5), 3) | |
XCTAssertEqual(case2.lowerBound(6), 4) | |
let case3: [Int] = [1, 3, 5, 7] | |
XCTAssertEqual(case3.lowerBound(0), 0) | |
XCTAssertEqual(case3.lowerBound(1), 0) | |
XCTAssertEqual(case3.lowerBound(2), 1) | |
XCTAssertEqual(case3.lowerBound(3), 1) | |
XCTAssertEqual(case3.lowerBound(4), 2) | |
XCTAssertEqual(case3.lowerBound(5), 2) | |
XCTAssertEqual(case3.lowerBound(6), 3) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment