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

import Foundation

struct AuD_14_01_InterpolationSearch {

    //a: sortiertes Array mit n Elementen, x gesuchter Wert
    static func InterpolationSearch(_ a: [Int], _ x: Int) -> Int? {
        let n = a.count
        var l = 0 //linker Rand des Suchraumes
        var r = n-1 //rechter Rand des Suchraumes
        while (l <= r) {
            if x < a[l] || x > a[r] {
                return nil
            }
            if a[l] == a[r] {
                if a[l] == x {
                    return l
                } else {
                    return nil
                }
            } else {
                let d_1 = x - a[l]
                let d_2 = a[r] - x
                let m = (d_1 * r + d_2 * l) / (d_1 + d_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 ... 99).map( { (i) in 2*i } )

    static func run() {
        for x in 0 ... 100 {
            if let pos = InterpolationSearch(a, x).map ({ (p: Int) in p.description }) {
                print("\(x) is at position \(pos)")
            } else {
                print("\(x) not found")
            }
        }
    }

}