07ex

/*
Zur Abgabe einen branch `iprg-b07` erstellen und pushen, in dem als einzige Datei die `07ex.c` liegt.
*/

/*
Um die Tests für dieses Blatt zu kompilieren und zu starten, führen Sie den folgenden Befehl aus:
cc -std=c11 -g -Wall -Werror 07ex_test.c -o 07ex_test.o -lm && ./07ex_test.o

Wir empfehlen, mit möglichst streng eingestelltem valgrind zu testen, denn so testen wir auch auf dem Server:
cc -std=c11 -g -Wall -Werror 07ex_test.c -o 07ex_test.o -lm && valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes ./07ex_test.o
*/

#include "sphinx.h"
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int answers = 0;
/*
Aufgabe 1:

Da spaziert man entspannt durch Theben, und plötzlich kommt eine Sphinx angeflogen
und spricht: "Ich habe mir ein Array mit n absteigend sortierten Zahlen überlegt (Zahlen
können mehrfach vorkommen). Du darfst mich nach dem Wert an 1 + log2(n) (aufgerundet) vielen
Positionen fragen. Und wenn du mir danach nicht sagen kannst, ob das Array die Zahl 12345
enthält, dann fresse ich dich.".

Geben Sie zurück, ob das Array der Sphinx die Zahl 12345 enthält. Um den Wert an Position `i`
zu erfragen, rufen Sie `sphinx_ask(s, i)` auf. Aber Achtung: Wenn Sie diese Funktion mehr als
1 + log2(n) (aufgerundet) mal aufrufen, stürzt das Programm fehlerhaft ab.
*/

int logarithmus(int a){
    int res = 0;
    if(a == 1) return 0;

    while(a){
        a/=2;
        res++;
    }
    return res;
}


bool descending_sphinx(Sphinx *s, size_t n){

    if(n==0) return false;
    else if(n==1){
        if(sphinx_ask(s,0) != 12345) return false;
        else return true;
    }
    else{
        int left = 0;
        int right = n-1;

        //printf("left = %d, right = %d\n", left, right);
        int pos = (left+right)/2; //der erste index nach dem wir fragen
        //printf("mitte = %d\n", pos);

        while(pos >= left && pos <= right){

            int num = sphinx_ask(s,pos);
            answers++;
            //if(answers > logarithmus(n)+1) break;
            if(num == 12345) return true;
            else if(num < 12345){ //die zahl ist kleiner als 12345 -> schauen im lonken teilarray
                //printf("die zahl ist kleiner als 12345 -> schauen im linken teilarray\n");
                right = pos - 1; //verschieben die rechte grenze, linke bleibt gleich
                //printf("left = %d, right = %d\n",left, right);
            }
            else if(num > 12345){
                //printf("die zahl ist groesser als 12345 -> schauen im linken teilarray\n");
                left = pos + 1; //verschieben die linke grenze, rechte bleibt gleich
                //printf("left = %d, right = %d\n",left, right);
            }

            //betrachteten index nochmal berechnen, da sich die grenzen geaendert haben
            pos = (left+right)/2;
            //printf("new position = %d\n", pos);
        }
        //wenn immer noch nichts gefunden / array grenzen ueberschritten oder anzahl der schritten ueberschritten -> return false
    }

    return false;

}