Floor And Ceil - C++ Solution

1. Introduction

This blog post discusses a search problem that is fundamental in algorithm design - finding the floor and ceiling of a given number in a sorted array. The floor of a number x is defined as the largest element in the array less than or equal to x, and the ceiling is the smallest element in the array greater than or equal to x.

Problem

Given a sorted array of integers, the task is to find the floor and ceiling of a specified number within the array. If the floor or ceiling doesn't exist, return -1 for that value.

2. Solution Steps

1. Implement binary search to find the floor of the given number.

2. Implement binary search to find the ceiling of the given number.

3. During the search, update the potential floor or ceiling based on the comparison with the target number.

4. Return the pair of floor and ceiling values found.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to find the floor of the target
int findFloor(const vector<int>& nums, int target) {
    int res = -1, low = 0, high = nums.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] <= target) {
            res = nums[mid];
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return res;
}

// Function to find the ceil of the target
int findCeil(const vector<int>& nums, int target) {
    int res = -1, low = 0, high = nums.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] >= target) {
            res = nums[mid];
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return res;
}

// Main function to find floor and ceil
pair<int, int> findFloorAndCeil(const vector<int>& nums, int x) {
    return {findFloor(nums, x), findCeil(nums, x)};
}

int main() {
    vector<int> nums = {1, 4, 6, 8, 9};
    int x = 2;
    auto [floor, ceil] = findFloorAndCeil(nums, x);
    cout << "Floor and Ceil: (" << floor << ", " << ceil << ")" << endl;
    return 0;
}

Output:

Floor and Ceil: (1, 4)

Explanation:

The program implements two binary searches to find the floor and ceiling of a target number in a sorted array. The findFloor function returns the largest element less than or equal to the target, and findCeil returns the smallest element greater than or equal to the target. For the input array [1, 4, 6, 8, 9] with target 2, the floor is 1 and the ceiling is 4. The function handles cases where either floor or ceiling doesn't exist, returning -1 for those scenarios.