int binarySearch(int[] preorder, int start, int end, int val) {
        int s = start;
        int e = end;
        while (s <= e) {
            int middle = (s + e)/2;
            if (preorder[middle] < val && (start == middle || preorder[middle - 1] > val)) {
                return middle;
            } else if (preorder[middle] < val) {
                e = middle - 1;
            } else {
                s = middle + 1;
            }
        }
        return -1;
    }
Check if given pre array sequence will create a binary search tree or not.

Idea is to keep minimal acceptable value. Any element in pre array should never be less
than minimal acceptable value. Values are popped from stack till they are less than pre[i]
Last popped value becomes new minimally acceptable vaue.

It does not work for duplicates

Time complexity - O(n)
https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/
Reference - http://www.geeksforgeeks.org/check-if-a-given-array-can-represent-preorder-traversal-of-binary-search-tree/
src/com/interview/tree/IsPreOrderArrayBST.java