IZLAZNI KOLOKVIJ - 26.01.2018. (B)

// 1. zadatak
void BinarnoPretrazivanje(int *polje, int velicinaPolja, int trazeniBroj) {
    int dg, gg, sredina, flag;
    dg = 0;
    gg = velicinaPolja - 1;
    sredina = (dg + gg) / 2;
    flag = 0;
    while (dg <= gg) {
        if (polje[sredina] == trazeniBroj) {
            cout << "Broj pronadjen" << endl;
            flag = 1;
            break;
        }
        else if (polje[sredina] < trazeniBroj) {
            dg = sredina + 1;
        }
        else if (polje[sredina] > trazeniBroj) {
            gg = sredina - 1;
        }
        sredina = (dg + gg) / 2;
    }
    if (flag == 0) {
        cout << "Broj nije pronadjen" << endl;
    }
}

// 2. zadatak
struct Node
{
    int data;
    struct Node* next;
};

bool find(struct Node* head, int n) {
    struct Node* p = head;
    int len = 0;

    // Pretrazivanje O(n)
    while (p != NULL) {
        if (p->data == n) {
            return true;;
        }
        len++;
        p = p->next;
    }

    // Na početak O(1)
    struct Node* front;
    front->data = n;
    front->next = head;
    head = front;

    // U sredinu O(n/2)
    p = head;
    int count = ((len % 2) == 0) ? (len / 2) : (len + 1) / 2;
    while (count-- > 1) {
        p = p->next;
    }
    struct Node* mid;
    mid->data = n;
    mid->next = p->next;
    p->next = mid;

    // Na kraj O(n)
    p = head;
    while (p->next != NULL) {
        p = p->next;
    }
    struct Node* end;
    end->data = n;
    p->next = end;
    end->next = NULL;

    return false;
}

// 3. zadatak
int Fibonacci(int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return 1;
    }

    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

// 4. zadatak
struct cvor {
    int x;
    struct cvor *left, *right;
};

void ubaci(struct cvor *r, struct cvor *p) {
    if ((r->right == NULL) && (p->x > r->x)) {
        r->right = p;
    }
    else if ((r->right != NULL) && (p->x > r->x)) {
        ubaci(r->right, p);
    }
    if ((r->left == NULL) && (p->x < r->x)) {
        r->left = p;
    }
    else if ((r->left != NULL) && (p->x < r->x)) {
        ubaci(r->left, p);
    }
}

void preOrder(struct cvor* root) {
    if (root == NULL){
        return;
    }
    else{
        printf("%d", root->x);
        preOrder(root->left);
        preOrder(root->right);
    }
}