binary search

gistfile1.txt

//: Playground - noun: a place where people can play

import UIKit

extension Array {
    func binarySearch<T: Comparable>(key: T, returnInsertionIndex: Bool = false) -> Int? {
        var range = 0..<self.count

        var midIndex: Int = 0
        var value: T?

        while range.startIndex < range.endIndex {
            // Find the middle point in the array within the given range
            midIndex = range.startIndex + (range.endIndex - range.startIndex) / 2

            let m = self[midIndex] as? T

            guard let midValue = m else {
                return nil
            }

            value = midValue

            if midValue == key {
                // If we found our search key, return the index
                return midIndex
            } else if midValue < key {
                // If the mdidle value is less than the key, look at the right half
                range = (midIndex + 1)..<range.endIndex
            } else {
                // If the midle value is greater than the key, look at the left half
                range = range.startIndex..<midIndex
            }
        }

        if let value = value, returnInsertionIndex {
            return value > key ? midIndex : midIndex + 1
        }

        return nil
    }
}

[0.0, 1.0, 3.2, 5.4].binarySearch(key: 1.1, returnInsertionIndex: true)

mdidle, midle = middle