diff options
Diffstat (limited to 'usth/ICT2.2/midterm/src/Search.java')
-rw-r--r-- | usth/ICT2.2/midterm/src/Search.java | 57 |
1 files changed, 57 insertions, 0 deletions
diff --git a/usth/ICT2.2/midterm/src/Search.java b/usth/ICT2.2/midterm/src/Search.java new file mode 100644 index 0000000..efb9e45 --- /dev/null +++ b/usth/ICT2.2/midterm/src/Search.java @@ -0,0 +1,57 @@ +import java.util.List; +import java.util.Comparator; + +public class Search +{ + public static final int NOT_FOUND = -1; + + public static int linear(List list, Object key) + { + for (int i = 0; i < list.size(); ++i) + if (key == null ? list.get(i) == null : key.equals(list.get(i))) + return i; + return NOT_FOUND; + } + + private static <T> + int binary(List<? extends Comparable<? super T>> list, T key, + int low, int high) + { + if (high < low) + return NOT_FOUND; + var mid = (low + high) / 2; + var cmp = list.get(mid).compareTo(key); + if (cmp < 0) + return binary(list, key, mid + 1, high); + if (cmp > 0) + return binary(list, key, low, mid - 1); + return mid; + } + + public static <T> + int binary(List<? extends Comparable<? super T>> list, T key) + { + return binary(list, key, 0, list.size()); + } + + private static <T> + int binary(List<? extends T> list, T key, Comparator<? super T> c, + int low, int high) + { + if (high < low) + return NOT_FOUND; + var mid = (low + high) / 2; + var cmp = c.compare(list.get(mid), key); + if (cmp < 0) + return binary(list, key, c, mid + 1, high); + if (cmp > 0) + return binary(list, key, c, low, mid - 1); + return mid; + } + + public static <T> + int binary(List<? extends T> list, T key, Comparator<? super T> c) + { + return binary(list, key, c, 0, list.size()); + } +} |