Searching: Check the ceiling in a sorted array

Problem Statement:

You are given a sorted array and a value x.

You need to find the index of ceiling of x, such that it is the smallest element in an array greater than or equal to x.

Example:

Input a[] = [1, 2, 3, 4, 6, 7, 8] x = 5

Output: 4

Smallest element greater than 5 is 6, index is 4

Solution 1: Brute force approach

Do a linear search and return the first element in the array that satisfies the condition.

Time Complexity: O(n)
Space Complexity: O(1)

Solution 2: Binary search

We an use binary search to get the result.

Below are the conditions:

If a[mid] < x then goto right.

If a[mid] >= x, then go to left side, and find the smaller value which is greater than or equal to x.

Time Complexity: O(log n)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <limits.h>

using namespace std;


int solution_1 (vector<int>& arr, int x) 
{   

    if(x <= arr[0]) 
        return 0; 
  
    for(int i = 0; i < arr.size() - 1; i++) 
    { 
        if(arr[i] == x) 
            return i; 
      
        if(arr[i] < x && arr[i+1] >= x) 
            return i+1; 
    }     

    return -1; 
} 


int solution_2 (vector<int>& arr, int x) 
{
    int lo = 0;
    int hi = arr.size() - 1;
    int res = -1;
    
    while (lo <= hi) 
    {
        int mid = lo + (hi - lo) / 2;
  
        if (arr[mid] < x)
            lo = mid + 1;      
        
        else 
        { 
            res = mid;   
            hi = mid - 1;
        }
    }
    return res;  
}

int main() 
{ 
    vector<int> arr = {1, 2, 3, 4, 6, 7, 8}; 
    int x = 5; 

    int index = solution_1 (arr, x); 
    if(index == -1) 
        cout << "False"; 
    else
        cout << "Index = " << arr[index]; 
    cout<<endl;
    index = solution_2 (arr, x); 
    if(index == -1) 
        cout << "False"; 
    else
        cout << "Index = " << arr[index];



    return 0; 
}

Output

Index = 6
Index = 6