 /*
T must implement the operators -, !=, ==, >=, <= and <
such that >=, <=, !=, == and < define a total order on T and
such that

is an int between 0 and k (inclusive) for any tl, tm, th in T with tl <= tm <= th, tl != th.arr must be sorted according to this ordering.\returns An index i such that arr[i] == key or -1 if there is no i that satisfies this.