educative.io

Educative

Why start is the ceiling of the number?

For answer of searchCeilingOfANumber(see below), I am not quite understand(based on the comments) why start is the ceiling of the number? could you help to explain a bit more detail? Thanks.
public static int searchCeilingOfANumber(int[] arr, int key) {
// since the loop is running until ‘start <= end’, so at the end of the while loop, ‘start == end+1’
// we are not able to find the element in the given array, so the next big number will be arr[start]
return start;

1 Like

I had the same question as you and realized that the reason is that

before start loop it checks

if(arr[end] < target)
    return -1;

this guarantees that the last element is always larger than or equals to target
so when exit loop the start will be the answer

Suppose we keep going until the last element, this is where start == mid == end as you see the photo in the solution.

Hope this help

I still don’t understand why start is the ceiling of the number, can someone explain further?

It is bit difficult to wrap your head around that solution. So I prefer following way of tackling this problem. Whenever higher value is available store it as current ceil, go left to find if there is a smaller ceil than that. With slight change it can be used for floor

public static int searchCeilingOfANumber(int[] arr, int key) {

    int start = 0;

    int end = arr.length - 1;

    

    int ceilIndex = -1;

    while(start <= end) {

      int middle = start + (end - start) / 2;

      if(key > arr[middle]) {

        start = middle + 1;

      }

      else {

        ceilIndex = middle;

        end = middle - 1;

      }

    }

    return ceilIndex;

  }
1 Like

At the end of while loop.
Start would have become equivalent to last end index itself.
The end + 1 is actually (mid - 1) + 1 basically the last index of the array.