educative.io

What if end > Integer.MAX_VALUE?

Courses
,
#1

I wonder what will happen if the size of the array is Integer.MAX_VALUE, and the item that we are looking for is the last one.
Will we have an overflow of the ‘end’ variable when we do the root ‘while’?

Let’s say we have an array […, Integer.MAX_VALUE]. The key is ‘Integer.MAX_VALUE’. Will the algorithm work?

  public static int search(ArrayReader reader, int key) {
    // find the proper bounds first
    int start = 0, end = 1;
    while (reader.get(end) < key) {
      int newStart = end + 1;
      end += (end - start + 1) * 2; // <- can overflow be here?
      start = newStart;
    }
    return binarySearch(reader, key, start, end);
  }
#2

I have the same question @Kostya. I am also thinking about what is happening if reader.get(end) returns -1 … probably the solution has a bug

1 Like
#3

Hi @Kostya

If the size of the array is Integer.MAX_VALUE and the item that you are looking for is the last one, then the index of that item will be Integer.MAX_VALUE - 1. Therefore, no issues.
Even if the size of the array is greater than Integer.MAX_VALUE, still we won’t have the problem because the lesson says:

if the array’s size is smaller than the index, it will return Integer.MAX_VALUE.

and it’s not possible to send a value of the index greater than the Integer.MAX_VALUE because the variable index will overflow.

#4

Hi @Horacio_Lopez

Why would there be a problem if reader.get(end) return a negative number? If the array contains negative numbers, then this function might return negative numbers, and it’s not an issue in my opinion.