Swift: Binary search for standard array?

by

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

More Related Contents:

  1. how to check if there is any string from index 0 to 5 in an array of type Any [closed]
  2. remove an index number from array
  3. How to check if an element is in an array
  4. How to sort an array of custom objects by property value in Swift
  5. Two-dimensional array in Swift
  6. How do I insert an element at the correct position into a sorted array in Swift?
  7. Shorthand to test if an object exists in an array for Swift?
  8. How to get list of common elements of 2 array in Swift?
  9. Swift sort an array with strings and numbers [duplicate]
  10. Flatten [Any] Array Swift
  11. How to remove an element from an array in Swift
  12. Is it possible to make an Array extension in Swift that is restricted to one class?
  13. Cannot convert value of type ‘Meme!’ to expected argument type ‘@noescape (Meme) throws -> Bool’
  14. Swift 3 2d array of Int
  15. Find Duplicate Elements In Array Using Swift
  16. How can I interleave two arrays?
  17. Swift: What’s the best way to pair up elements of an Array
  18. Swift 4 JSON Codable – value returned is sometimes an object, others an array
  19. swift: modifying arrays inside dictionaries
  20. How can I convert an array to a tuple?
  21. How to stable sort an array in swift?
  22. YAML equivalent of array of objects in JSON
  23. New Array from Index Range Swift
  24. Iterate over two arrays simultaneously
  25. Why does the reverse() function in the Swift standard library return ReverseRandomAccessCollection?
  26. Compare 2 arrays and list the differences – Swift
  27. In Swift how can I sort one array based on another array?
  28. Concatenate Swift Array of Int to create a new Int
  29. Find the first element in a sorted array that is greater than the target
  30. check if all elements of an array have the same value in Swift

Leave a Comment