Lowest value in range

Question

I would like to find the lowest value in some range.
Do I have to iterate array each time or is there any dynamic method?

Lets say I have input array:

index: 0 1 2 3 4 5 6 7
value: 1 4 6 1 6 7 2 3

and then I have to choose smallest in range < a,b > (inclusive). For example:

min(0,7) = 1
min(0,2) = 1
min(4,6) = 2
min(1,2) = 4

Im interested in the fastest solution, it would be the best to get the results in constant time.

Array won't be changed in meantime.

Answer 1

If you are going to perform multiple queries over the same set of numbers then you will want to construct a Cartesian Tree.

Cartesian trees may be used as part of an efficient data structure for range minimum queries, a range searching problem involving queries that ask for the minimum value in a contiguous subsequence of the original sequence.

As the article says, the queries can be performed in constant time.

Answer 2

You can use segment tree for this question. This is one of the best tutorial on segment tree and range minimum query.

I am giving JAVA implementation and the code is self explanatory, please let me know if you have any doubts.

public class SegmentTree {

    private int[] array;
    private int length;

    public static SegmentTree initialize(int[] a) {
        return new SegmentTree(a);
    }

    private SegmentTree(int[] a) {
        length = a.length - 1;
        int l = (int) (Math.log(a.length) / Math.log(2));
        l = (int) (Math.pow(2, l + 1) * 2 - 1);
        array = new int[l];
        initialize(a, 0, a.length - 1, 0);
    }

    private int initialize(int[] a, int p, int r, int index) {
        if (p == r) {
            array[index] = a[p];
            return a[p];
        }
        int q = p + (r - p) / 2;
        array[index] = Math.min(initialize(a, p, q, 2 * index + 1), initialize(a, q + 1, r, 2 * index + 2));
        return array[index];
    }

    public int findMin(int p, int r) {
        return _findMin(p, r, 0, length, 0);
    }

    private int _findMin(int qs, int qe, int ss, int se, int i) {
        if (qs <= ss && se <= qe) {
            return array[i];
        }
        if (qs > se || qe < ss) {
            return Integer.MAX_VALUE;
        }
        int q = ss + (se - ss) / 2;
        return Math.min(_findMin(qs, qe, ss, q, 2 * i + 1), _findMin(qs, qe, q + 1, se, 2 * i + 2));
    }

    private void print() {
        int index = 0;
        for (int k : array) {
            System.out.println(index + ":" + k);
            index++;
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 34, 5, 6, 78, 5, 67, 89};
        SegmentTree s = initialize(a);
        System.out.println(s.findMin(2, 4));
    }
}