Floor and Ceil in Sorted Array in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of floor and ceil search in sorted array

What is the output of the following C++ code that finds floor and ceil of a target in a sorted array?

DSA C++

int floorIndex(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1, floor = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) {
            floor = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return floor;
}

int ceilIndex(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1, ceil = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] > target) {
            ceil = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ceil;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9};
    int target = 6;
    int f = floorIndex(arr, target);
    int c = ceilIndex(arr, target);
    cout << "Floor index: " << f << ", Ceil index: " << c << endl;
    return 0;
}

A Floor index: 3, Ceil index: 2

B Floor index: 1, Ceil index: 4

C Floor index: 2, Ceil index: 3

D Floor index: -1, Ceil index: -1

💡 Hint

Remember floor is the greatest element less than or equal to target, ceil is the smallest element greater than or equal to target.

The floor of 6 in the array {1,3,5,7,9} is 5 at index 2, and the ceil is 7 at index 3.

🧠 Conceptual

intermediate

Understanding floor and ceil in sorted arrays

In a sorted array, what does the floor of a target value represent?

A The element exactly equal to the target if it exists, otherwise -1

B The greatest element less than or equal to the target

C The smallest element greater than or equal to the target

D The average of the smallest and greatest elements in the array

💡 Hint

Floor is about the closest smaller or equal value to the target.

Floor is defined as the greatest element in the array that is less than or equal to the target value.

🔧 Debug

advanced

Identify the error in floor function implementation

What error will the following floor function cause when called with target=4 on array {1,3}?

DSA C++

int floorIndex(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1, floor = -1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) {
            floor = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return floor;
}

A Returns incorrect floor index 0

B Throws runtime error due to invalid index

C Runs into infinite loop

D Returns -1 correctly indicating no floor found

💡 Hint

Check the loop condition and how left and right pointers move.

The loop condition 'left < right' causes the loop to exit prematurely when left == right without processing the final position, resulting in floor index 0 (value 1) instead of 1 (value 3).

❓ Predict Output

advanced

Output of ceil function with target present in array

What is the output of the following code snippet?

DSA C++

vector<int> arr = {2, 4, 6, 8, 10};
int target = 8;
int left = 0, right = arr.size() - 1, ceil = -1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
        ceil = mid;
        break;
    } else if (arr[mid] > target) {
        ceil = mid;
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}
cout << "Ceil index: " << ceil << endl;

A Ceil index: 4

B Ceil index: 2

C Ceil index: -1

D Ceil index: 3

💡 Hint

If target is present, ceil index should be the index of target itself.

Since 8 is at index 3, but mid calculation and break happen at mid=2 or 3? Actually mid=2 (value 6) < 8, left=3, then mid=3 (value 8) == target, so ceil=3.

🧠 Conceptual

expert

Floor and Ceil behavior on empty array

What are the floor and ceil indices returned by the standard binary search approach when the input array is empty?

A Both floor and ceil return -1 indicating no elements

B Floor returns 0, Ceil returns 0

C Floor returns -1, Ceil returns 0

D Both floor and ceil cause runtime error due to invalid access

💡 Hint

Think about the initial values and loop conditions when array size is zero.

With empty array, no elements exist, so floor and ceil indices remain at initialized -1 indicating no valid floor or ceil.

Practice

1. What does the floor of a number mean in a sorted array context?

easy

A. The greatest element less than or equal to the number

B. The smallest element greater than the number

C. The average of all elements less than the number

D. The smallest element less than the number

Solution

1. Step 1: Understand floor definition in sorted array

   The floor of a number is the greatest element in the array that is less than or equal to the given number.

2. Step 2: Compare options with definition

   The greatest element less than or equal to the number matches the definition exactly. Other options describe different concepts.

3. Final Answer:

   The greatest element less than or equal to the number -> Option A

4. Quick Check:

   Floor = greatest ≤ number [OK]

Hint: Floor is always ≤ number, pick greatest such element [OK]

Common Mistakes:

• Confusing floor with ceil
• Choosing smallest element greater than number
• Thinking floor is average or exact match only

2. Which of the following is the correct C++ function signature to find the floor of a number in a sorted array?

easy

A. int findFloor(int arr[], int n, int x);

B. void findFloor(int arr[], int n, int x);

C. int findFloor(int arr, int n, int x);

D. int findFloor(int arr[], int x);

Solution

1. Step 1: Analyze function parameters

   The function needs the array, its size, and the target number to find floor.

2. Step 2: Check each option's signature

   int findFloor(int arr[], int n, int x); correctly uses array pointer, size, and target number. void findFloor(int arr[], int n, int x); returns void which is incorrect. int findFloor(int arr, int n, int x); uses int arr instead of array. int findFloor(int arr[], int x); misses size parameter.

3. Final Answer:

   int findFloor(int arr[], int n, int x); -> Option A

4. Quick Check:

   Correct signature includes array, size, target [OK]

Hint: Function needs array, size, and target number [OK]

Common Mistakes:

• Omitting array size parameter
• Using wrong array type
• Returning void instead of int

3. What is the output of the following code snippet?

int arr[] = {1, 3, 5, 7, 9};
int n = 5;
int x = 6;
int floor = -1;
for (int i = 0; i < n; i++) {
  if (arr[i] <= x) floor = arr[i];
  else break;
}
std::cout << floor;

medium

A. 6

B. 7

C. 5

D. -1

Solution

1. Step 1: Trace the loop and condition

   Loop checks each element ≤ 6. Elements 1, 3, 5 satisfy condition, floor updates to 5. When arr[i] = 7, condition fails and loop breaks.

2. Step 2: Determine final floor value

   Floor remains 5 after loop ends.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Floor of 6 in array = 5 [OK]

Hint: Floor is last element ≤ target before break [OK]

Common Mistakes:

• Choosing 6 which is not in array
• Choosing 7 which is > 6
• Not updating floor correctly

4. Find the error in the following code to find the ceil of a number in a sorted array:

int findCeil(int arr[], int n, int x) {
  int ceil = -1;
  for (int i = 0; i < n; i++) {
    if (arr[i] >= x) {
      ceil = arr[i];
    }
  }
  return ceil;
}

medium

A. It uses wrong comparison operator

B. It returns -1 even if ceil exists

C. It should return floor instead of ceil

D. It does not return the smallest element ≥ x

Solution

1. Step 1: Understand the loop logic

   The loop updates ceil whenever arr[i] ≥ x, but does not stop or check for smallest such element.

2. Step 2: Identify the error

   Because it keeps updating, it ends with the last element ≥ x, not the smallest. It should break or track minimum.

3. Final Answer:

   It does not return the smallest element ≥ x -> Option D

4. Quick Check:

   Ceil = smallest ≥ x, code returns largest ≥ x [OK]

Hint: Ceil must be smallest ≥ target, not last found [OK]

Common Mistakes:

• Not breaking loop after first valid ceil
• Updating ceil without checking if smaller
• Confusing floor and ceil logic

5. Given a sorted array arr = {2, 4, 6, 8, 10}, what are the floor and ceil of x = 5? Choose the correct pair.

hard

A. Floor = 5, Ceil = 6

B. Floor = 4, Ceil = 6

C. Floor = 4, Ceil = 5

D. Floor = 6, Ceil = 8

Solution

1. Step 1: Find floor of 5 in array

   Floor is greatest element ≤ 5. Elements ≤ 5 are 2 and 4, greatest is 4.

2. Step 2: Find ceil of 5 in array

   Ceil is smallest element ≥ 5. Elements ≥ 5 are 6, 8, 10, smallest is 6.

3. Final Answer:

   Floor = 4, Ceil = 6 -> Option B

4. Quick Check:

   Floor ≤ 5 = 4, Ceil ≥ 5 = 6 [OK]

Hint: Floor ≤ x, Ceil ≥ x; pick closest elements [OK]

Common Mistakes:

• Assuming floor or ceil must equal x
• Choosing elements not in array
• Mixing floor and ceil values