Бинарный поиск интервала

#алгоритм #поиск

Есть массив 1 2 3 ... N. Известно, что этот массив можно разбить на три интервала
[1 2 .. .L-2 L-1], [L L+1 ... R-1 R], [R+1 R+2 ... N-1 N], (L<=R) так что каждый элемент
из своего интервала дает определенный результат в функции f. f(1)=f(2)=...f(L-1), f(L)=f(L+1)=...f(R).
f(R+1)=f(R+2)=...f(N).   

Как за logN (какой-нибудь модифицированный бинарный поиск) найти эти L и R?
    

Ответы

Ответ 1

Извиняюсь что на Джаве.

public class App {
    public static void main(String[] args) {

        int[] arr = {1,1,2,2,2,2,3,3};

        Interval interval = find(0, arr.length - 1, i -> arr[i]);

        System.out.println(interval);

    }

    static Interval find(int start, int finish, Function f) {
        int intStart = findStart(start, finish, f) + 1;
        int intEnd = findStart(intStart, finish, f);
        return new Interval(intStart, intEnd);
    }

    private static int findStart(int start, int finish, Function f) {
        int a = start;
        int b = finish;
        Object aO = f.apply(start);
        Object bO = f.apply(finish);
        while (a + 1 < b) {
            int m = (a + b) / 2;
            Object mO = f.apply(m);
            if (aO.equals(mO)) {
                a = m;
            } else {
                assert bO.equals(mO);
                b = m;
            }
        }
        return a;
    }

    @Data
    private static class Interval {
        private final int intStart;
        private final int intEnd;
    }
}