/**
 * 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_02_BinarySearch {

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

    // oder generisch:
    static func BinarySearchG<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] {
                return m
            }
            if x < a[m] {
                r = m - 1
            } else {
                l = m + 1
            }
        }
        return nil
    }

    static let a: [Int] = (0 ... 49).map({ (i) in i * 2 })

    static func run() {

        for x in 0 ... 100 {
            let posOfx: String = BinarySearch(a, x)?.description ?? "not found"
            print("\(x) => pos: \(posOfx)")
        }

        for x in 0 ... 100 {
            let posOfx: String = BinarySearchG(a, x)?.description ?? "not found"
            print("\(x) => pos: \(posOfx)")
        }

    }

}