Searching with Binary Search

In the dynamic-array chapter, DynamicArray.indexOf has to scan linearly, because the elements are in no particular order. A SortedArray is in order, so it can find a value with binary search instead.

We do not need to write a new search for this. The class already has one: the insertionPoint method that add uses. If the value is present, it returns the value’s index. If the value is absent, it returns the index where the value would have to go. So the index it returns is the only place an equal element could possibly be. Look at that index. If an equal element is there, the value is present. If it is not, the value is not in the array at all.

public int indexOf(T value) {
  int i = insertionPoint(value);
  if (i < size && arr[i].equals(value)) {
    return i;  // an equal element really is at that spot
  }
  return -1;  // not present
}

public boolean contains(T value) {
  return indexOf(value) != -1;
}

The i < size check comes first because insertionPoint can legitimately return size, when the value is larger than everything in the array and would belong at the very end. There is no element at that index to compare against, so we have to test the bound before reading arr[i].

This indexOf is faster than DynamicArray.indexOf because it uses binary search, but it comes with a tradeoff. The add method is slower than DynamicArray.add, because it has to find the insertion point and shift elements right. The client has to decide which is more important: fast search or fast add.