Lower Bound

LowerBound.java

import java.util.*;

public class LowerBound {

	private LowerBound() {}

	final static class Node {
		Node left, right;
		final int val;
		public Node(int val) {
			this.val = val;
		}

		public static Node fromList(int... vals) {
			Arrays.sort(vals);
			return fromList(vals, 0, vals.length);
		}

		private static Node fromList(int[] arr, int start, int end) {
			if (start == end) return null;
			int mid = (start + end) / 2;
			Node n = new Node(arr[mid]);
			n.left = fromList(arr, start, mid);
			n.right = fromList(arr, mid+1, end);
			return n;
		}
	}

	public static void main(String[] args) {
		Node n = Node.fromList(1, 2, 3, 4, 5, 6, 7);
		for (int i : Arrays.asList(1, -2, 4, 6, 9, 119, 20, -10)) {
			System.out.printf("%d -> %s\n", i, lowerBound(n, i));
		}
	}


	/**
	 * get the lower bound of val in the tree
	 *
	 * @return lower bound if available, else null
	 */
	public static Integer lowerBound(Node tree, int val) {
		Integer result = null;
		while (tree != null) {
			int v = tree.val;
			if (v >= val) {
				tree = tree.left;
			} else {
				result = v;
				tree = tree.right;
			}
		}
		return result;
	}


}