// 2. hét – A gyakorlati feladatok megoldásai
// Futtatás: java Exercises02.java
public class Exercises02 {

    // F1. Maximumkiválasztás – O(n). A legnagyobb elem indexét adja vissza.
    static int maxIndex(int[] a) {
        int max = 0;
        for (int i = 1; i < a.length; i++) {
            if (a[i] > a[max]) max = i;
        }
        return max;
    }

    // F2. Megszámlálás – O(n): hány eleme egyenlő x-szel?
    static int countOf(int[] a, int x) {
        int c = 0;
        for (int v : a) {
            if (v == x) c++;
        }
        return c;
    }

    // F3. Az x első előfordulása RENDEZETT tömbben, ismétlődő elemekkel – O(log n).
    // Ha megtaláltuk, nem állunk meg, hanem balra keresünk tovább.
    static int firstOccurrence(int[] a, int x) {
        int lo = 0, hi = a.length - 1, result = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] == x) {
                result = mid;
                hi = mid - 1;
            } else if (a[mid] < x) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return result;
    }

    // F4. Beszúrási hely: az első index, ahol a[i] >= x – O(log n).
    // (Ide kellene beszúrni x-et, hogy a tömb rendezett maradjon.)
    static int lowerBound(int[] a, int x) {
        int lo = 0, hi = a.length; // félig nyitott intervallum: [lo, hi)
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    // F5. Egész négyzetgyök bináris kereséssel: a legnagyobb r, amelyre r*r <= n.
    static long isqrt(long n) {
        long lo = 0, hi = n, r = 0;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            if (mid <= n / Math.max(mid, 1)) { // mid*mid <= n, túlcsordulás nélkül
                r = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return r;
    }

    // F6. Számkitalálós játék: a gép 1..1000 között hány kérdésből talál ki egy számot?
    static int guessSteps(int secret, int max) {
        int lo = 1, hi = max, steps = 0;
        while (true) {
            int mid = lo + (hi - lo) / 2;
            steps++;
            if (mid == secret) return steps;
            if (mid < secret) lo = mid + 1;
            else hi = mid - 1;
        }
    }

    public static void main(String[] args) {
        int[] a = { 4, 9, 2, 9, 7, 1, 9 };
        System.out.println("F1. maxIndex = " + maxIndex(a));
        System.out.println("F2. countOf(9) = " + countOf(a, 9));

        int[] s = { 1, 2, 2, 2, 5, 7, 7, 9 };
        System.out.println("F3. firstOccurrence(2) = " + firstOccurrence(s, 2) + ", firstOccurrence(7) = " + firstOccurrence(s, 7));
        System.out.println("F4. lowerBound(6) = " + lowerBound(s, 6) + ", lowerBound(0) = " + lowerBound(s, 0) + ", lowerBound(10) = " + lowerBound(s, 10));
        System.out.println("F5. isqrt(99) = " + isqrt(99) + ", isqrt(1_000_000_000_000) = " + isqrt(1_000_000_000_000L));
        int worst = 0;
        for (int sec = 1; sec <= 1000; sec++) worst = Math.max(worst, guessSteps(sec, 1000));
        System.out.println("F6. 1..1000 között legfeljebb " + worst + " kérdés kell");
    }
}