Skip to content

Instantly share code, notes, and snippets.

@jimexist
Created March 30, 2014 02:49
Show Gist options
  • Save jimexist/9866650 to your computer and use it in GitHub Desktop.
Save jimexist/9866650 to your computer and use it in GitHub Desktop.
Lower Bound
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment