educative.io

Educative

Why cant we do the following for this question:

public static int search(ArrayReader reader, int key) {

int start = 0, end = key;
while (start <= end) {
  int mid = start + (end - start) / 2;
  if(reader.get(mid) == Integer.MAX_VALUE){
    mid = start + (mid -start)/2;
  }
  if (key < reader.get(mid)) {
    end = mid - 1;
  } else if (key > reader.get(mid)) {
    start = mid + 1;
  } else { // found the key
    return mid;

  }
}
return -1;

}

@Anumita_Verma start and end have to be indices, so end can’t be a key. That’s a major flaw in assumption. Always be clear about what variables mean.
May be your assumption if key is say 1000 it will be at index 1000, it can be at index 2000 because of repeating or negative numbers before it. But we can’t determine index using the key.

1 Like