Consider the following variant of the findIndex method of

Authors:

Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser

Chapter:

Maps, Hash Tables, And Skip Lists

Exercise:

Exercises

Question:21 | ISBN:9781118771334 | Edition: 6

Question

Consider the following variant of the findIndex method of the SortedTableMap
class, originally given in Code Fragment 10.11:
1 private int findIndex(K key, int low, int high) {

2 if (high < low) return high + 1

3 int mid = (low + high) / 2;
4 if (compare(key, table.get(mid)) < 0)
5 return findIndex(key, low, mid − 1);
6 else
7 return findIndex(key, mid + 1, high);
8 }
Does this always produce the same result as the original version? Justify your
answer.