Table Of Contents

1. Introduction
2. Problem Statement
3. Challenge In this Problem
4. Brute Force Approach
5. Binary Search aproach
6. Simple Inbuilt function Usage
7. Conclusions

Introduction

The problem at hand involves finding the ceil, which is the smallest element in a sorted array that is greater than or equal to a given value. This problem presents a unique twist on the conventional search problem, emphasizing the need for an efficient solution to handle large datasets. We will explore different approaches, including brute-force linear search and optimized binary search methods, to efficiently tackle this problem.

Problem Statement

You are given a sorted array of integers and a target value 'x'. Your task is to find the lower bound, which is the smallest element in the array that is greater than or equal to 'x'. This element is commonly referred to as the "ceiling" of 'x" in the given array.

Write a function or algorithm to efficiently solve this problem. Your solution should take into account that the array is sorted, which provides an opportunity for an optimized search strategy.

Input:

An integer 'N' representing the number of elements in the array.
An array 'arr' of 'N' distinct integers, sorted in ascending order.
An integer 'x' representing the target value.

Output:

Return the index of the smallest element in the array 'arr' that is greater than or equal to 'x'. If no such element exists in the array, return -1.

Example 1:

Input:
N = 4
arr[] = {1, 2, 2, 3}
x = 2

Output:
1

Explanation:
In the given array 'arr', index 1 corresponds to the smallest element that is greater than or equal to 'x' (i.e., arr[1] = 2).

Example 2:

Input:
N = 5
arr[] = {3, 5, 8, 15, 19}
x = 9

Output:
3

Explanation:
In the given array 'arr', index 3 corresponds to the smallest element that is greater than or equal to 'x' (i.e., arr[3] = 15).

Note:

Ensure that your solution is efficient and takes advantage of the fact that the array is sorted.
If no element in the array is greater than or equal to 'x', return -1 to indicate that there is no lower bound (ceiling) value.

Challenge:

Solve this problem with a time complexity of O(log N) or better, where N is the number of elements in the array.

Brute-Force Approach

Our strategy involves traversing the array starting from the beginning. During this traversal, each element will be compared with the target value, 'x.' The index, 'i,' where the condition 'arr[i] >= x' is first satisfied will be the answer.

Finding the Lower Bound with Linear Search:

1)Start by comparing 'x' with the first element in the sorted array.

2)If 'x' is smaller or equal to the first element, return 0 (the index of the first element) as the answer.

3)If 'x' is greater than the first element, proceed to a linear search.

4)During the linear search:
Compare 'x' with each element in the array one by one.
Look for the index 'i' where 'x' falls between 'arr[i]' and 'arr[i+1]'.
Once you find such an index, return 'i' as the answer.

5)If the entire array is searched and no suitable index 'i' is found, return -1 to indicate that there is no element in the array greater than or equal to 'x'.

CODE :

#include <iostream> 
using namespace std;

int findLowerBound(int arr[], int size, int target) {
    if (target <= arr[0])
        return 0;

    for (int i = 0; i < size; i++) {
        if (arr[i] == target)
            return i;

        if (arr[i] < target && (i + 1 < size) && arr[i + 1] >= target)
            return i + 1;
    }

    return -1;
}

int main() {
    int size;
    cout << "Enter the size of the array: ";
    cin >> size;

    int array[size];
    cout << "Enter the elements of the array in ascending order: ";
    for (int i = 0; i < size; ++i) {
        cin >> array[i];
    }

    int searchValue;
    cout << "Enter the target value: ";
    cin >> searchValue;

    int result = findLowerBound(array, size, searchValue);

    if (result == -1)
        cout << "No ceil value found for " << searchValue << " in the array.";
    else
        cout << "The ceil of " << searchValue << " is " << array[result];

    return 0;
}

The findLowerBound function searches for the "lower bound" of a target value within a sorted array. It starts by checking if the target is smaller or equal to the first element; if so, it returns the index of the first element. Otherwise, it proceeds with a linear search through the array, looking for the index where the target falls between two adjacent elements. Once found, it returns that index as the lower bound. If no such index is found during the search, it returns -1 to indicate that there is no lower bound in the array for the given target value.

In the main function, the code begins by prompting the user to input the size of an integer array. It then creates an array of the specified size and asks the user to input its elements in ascending order. Afterward, the program prompts the user to input a target value. The code calls the findLowerBound function. Depending on the result from this function, the code either prints a message indicating that there's no suitable "ceil" value in the array for the target value or provides the index and value found as the "ceil."

OUTPUT :

Enter the size of the array: 7
Enter the elements of the array in ascending order: 2 4 6 8 10 12 14
Enter the target value: 13
The ceil of 13 is 14

Complexity analysis

Time Complexity: O(N) - In the worst case, the algorithm examines the entire array, as it follows a linear search pattern.
N = size of the given array.

Space Complexity: O(1) - The algorithm uses a fixed amount of memory, irrespective of the array's size, making it memory-efficient.

Binary Search Approach

Optimal Approach (Using Binary Search)

To tackle this problem with a Binary search approach, we take advantage of the fact that the array is sorted.In our quest to efficiently find the lower bound in a sorted array, we employ the Binary Search algorithm. This approach optimizes the process and enhances the time complexity by following these steps:

1. Initializing Pointers and 'ans':

• We initialize two pointers, 'low' and 'high', and a variable 'ans' set to 'n,' which represents the array's size. The 'ans' variable is our initial fallback in case we don't find an index during the search.

2. Placing Pointers:

• Initially, we position 'low' at the first index and 'high' at the last index of the array.

3. Calculating 'mid':

• The 'mid' value is computed using the formula: mid = (low + high) // 2 (with '//' representing integer division).

4. Comparing arr[mid] with x:

• We encounter two distinct cases:
  • Case 1 - If arr[mid] >= x:
    • In this scenario, it suggests that the 'mid' index might be our answer. We update the 'ans' variable with 'mid' and proceed to search in the left half of the array, eliminating the right half.
  • Case 2 - If arr[mid] < x:
    • Here, 'mid' cannot be our answer as we need to find a larger element. Consequently, we discard the left half and focus our search on the right half of the array.

This iterative process continues until the 'low' pointer surpasses the 'high' pointer, ultimately leading to the discovery of the lower bound. The implementation of this Binary Search approach dramatically enhances the efficiency of finding the lower bound in a sorted array, resulting in a more favorable time complexity.

CODE :

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

int findLowerBound(std::vector<int> array, int size, int target) {
    int left = 0, right = size - 1;
    int result = -1;

    while (left <= right) {
        int mid = (left + right) / 2;

        if (array[mid] >= target) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return result
}

int main() {
    vector<int> numbers;
    int size, searchValue;

    cout << "Enter the size of the array: ";
    cin >> size;

    cout << "Enter the elements of the array in ascending order: ";
    for (int i = 0; i < size; ++i) {
        int num;
        cin >> num;
        numbers.push_back(num);
    }

    cout << "Enter the target value: ";
    cin >> searchValue;

    int result = findLowerBound(numbers, size, searchValue);
    
    if (result != -1) {
        cout << "The ceil value index for " << searchValue << " is: " << result << endl;
    } else {
        cout << "No ceil value found for " << searchValue << " in this array" << endl;
    }

    return 0;
}

findLowerBound Function:

We take a vector of integers array, its size size, and a target value target as parameters.
We initializes two pointers, left and right, at the beginning and end of the array, and a variable result to -1.
Inside a while loop that continues as long as left is less than or equal to right, it calculates the middle index mid.
If the element at the middle index array[mid] is greater than or equal to the target target, it updates the result with mid and adjusts right to mid - 1 to explore the left half of the array. If not, it adjusts left to mid + 1 to explore the right half.
Finally, the function returns the result, which holds the index of the element that is the lower bound (the smallest element greater than or equal to the target).
main Function:

In the main function, a vector of integers numbers is declared along with variables size and searchValue for user input.
The user is prompted to input the size of the array and the elements of the array in ascending order. The elements are pushed into the numbers vector.
The user is then prompted to input the target value.
The findLowerBound function is called with the numbers vector, size, and searchValue as arguments, and the result is stored in the result variable.
Depending on the value of result, the code prints either the index of the lower bound for the target value or a message indicating that no suitable "ceil" value was found in the array.

OUTPUT :

Enter the size of the array: 7
Enter the elements of the array in ascending order: 2 4 6 8 10 12 14
Enter the target value: 7
The ceil value for 7 is: 8

Complexity analysis

Time Complexity: O(logN) - Thanks to Binary Search, the algorithm efficiently finds the lower bound in a sorted array.
N = size of the given array.

Space Complexity: O(1) - The algorithm uses a fixed amount of memory, regardless of the array's size, making it memory-efficient.

Using C++ STL lower_bound Function

In C++, the lower_bound method is employed to obtain an iterator pointing to the first element within a specified range [first, last] with a value greater than or equal to the provided value 'val'. In essence, this function returns an iterator pointing to the smallest number that is the next greater or equal value to the specified 'val.' If there are multiple values equal to 'val' in the range, lower_bound provides the iterator pointing to the first occurrence of such a value. This method is a valuable tool in C++ for efficiently searching for elements in sorted containers like vectors or arrays.

CODE :

#include <iostream>
#include <vector>
#include <algorithm> // Required for std::lower_bound
using namespace std;

int lowerBound(vector<int> arr, int x) {
    int ans = lower_bound(arr.begin(),arr.end(),x)- arr.begin();
	return ans;
}

int main() {
    vector<int> numbers;
    int size, searchValue;

    cout << "Enter the size of the array: ";
    cin >> size;

    cout << "Enter the elements of the array in ascending order: ";
    for (int i = 0; i < size; ++i) {
        int num;
        cin >> num;
        numbers.push_back(num);
    }

    cout << "Enter the target value: ";
    cin >> searchValue;

    int result = lowerBound(numbers, searchValue);
    
    if (result != size) {
        cout << "The ceil value index for " << searchValue << " is: " << result << endl;
    } else {
        cout << "No ceil value found for " << searchValue << " in this array" << endl;
    }

    return 0;
}

lower_bound(arr.begin(), arr.end(), x):

--This part of the code invokes the std::lower_bound function. It takes three arguments:
arr.begin(): An iterator pointing to the beginning of the vector arr.
arr.end(): An iterator pointing to one position past the end of the vector arr. This represents the range in which the function will search.
x: The target value that we want to find the lower bound for.

- arr.begin():

--After lower_bound has identified the lower bound element's iterator within the range, this code subtracts arr.begin() from that iterator.
The result of this subtraction operation effectively gives us the index of the lower bound element within the vector.

OUTPUT :

Enter the size of the array: 7
Enter the elements of the array in ascending order: 2 4 6 8 10 12 14
Enter the target value: 7
The ceil for 7 is: 8

Complexity analysis :

Time Complexity: O(logN) - N is the size of given array.

Space Complexity : O(1).

Conclusion

In summary, when it comes to finding the ceil in a sorted array:

• Linear Search: Simple but less efficient (O(N)) for larger datasets.
• Binary Search: Highly efficient with logarithmic time complexity (O(log N)), ideal for sorted arrays.
• STL's lower_bound: Concise and efficient, especially in C++ applications.

Understanding the problem context is crucial. For small or unsorted datasets, a linear search works. For larger sorted arrays, opt for binary search or STL's lower_bound for efficiency. The choice depends on the problem's requirements and programming context. Happy coding!