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.