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.

Answer 1

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 

Answer 2

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