Although keys in a map are distinct, the binary search algorithm can be applied in a more general setting in which an array stores possibly duplicative elements in nondecreasing order. Consider the goal of identifying the index of the leftmost element with key greater than or equal to given k. Does the findIndex method as given in Code Fragment 10.11 guarantee such a result? Does the findIndex method as given in Exercise R-10.21 guarantee such a result? Justify your answers.

Transcribed Image Text:

public class Sorted TableMap extends AbstractSortedMap { private ArrayList> table public Sorted TableMap() { super(); } public Sorted TableMap(Comparator comp) { super(comp); } /** Returns the smallest index for range table[low.high] inclusive storing an entry with a key greater than or equal to k (or else index high+1, by convention). */ private int findIndex(K key, int low, int high) { if (high < low) return high + 1; int mid = (low + high) / 2; int comp = compare(key, table.get(mid)); if (comp == 0) return mid; else if (comp < 0) return findlndex(key, low, mid – 1); // answer is left of mid (or possibly mid) else new ArrayList<>((); // no entry qualifies 10 11 // found exact match 12 13 14 15 return findlndex(key, mid + 1, high); // answer is right of mid } /** Version of findIndex that searches the entire table */ private int findlndex(K key) { return findIndex(key, 0, table.size() – 1); } /** Returns the number of entries in the map. */ public int size() { return table.size(); } /** Returns the value associated with the specified key (or else null). */ public V get(K key) { int j = findlndex(key); if (j == size() || compare(key, table.get(j)) != 0) return null; // no match return table.get(j).getValue( ); 16 17 18 19 20 21 22 23 24 25 26 27 /** Associates the given value with the given key, returning any overridden value.*/ public V put(K key, V value) { int j = findlndex(key); if (j < size() && compare(key, table.get(j)) == 0) return table.get(j).setValue(value); table.add(j, new MapEntry(key, value)); return null; } /** Removes the entry having key k (if any) and returns its associated value. */ public V remove(K key) { int j = findlndex(key); if (j == size() || compare(key, table.get(j)) != 0) return null; // no match return table.remove(j).getValue(); } 28 29 30 // match exists 31 32 // otherwise new 33 34 35 36 37 38 39 40 41