/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 12, Teilen und Herrschen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_12_03_BinarySearchLeftRight {

    static func BinarySearchLeft<A: Comparable>(_ a: [A], _ x: A) -> Int {
        var l = 0
        var r = a.count - 1
        while (l <= r) {
            let m: Int = (l + r) / 2
            if x <= a[m] {
                r = m - 1
            } else {
                l = m + 1
            }
        }
        return l
    }

    static func BinarySearchRight<A: Comparable>(_ a: [A], _ x: A) -> Int {
        var l = 0
        var r = a.count - 1
        while (l <= r) {
            let m: Int = (l + r) / 2
            if x < a[m] {
                r = m - 1
            } else {
                l = m + 1
            }
        }
        return r
    }

    static let a: [Int] = [0, 3, 3, 5, 5, 5, 5, 8, 8, 12]

    static func run() {
        for x in -2...14 {
            print("\(x) L =>\t\(BinarySearchLeft(a, x))\tR => \(BinarySearchRight(a, x))")
        }
    }
}