Finding Floor and Ceil Values in a Sorted Array using Improved Binary Search

Given a sorted array and a value x, we need to find floor and ceil value of x in the array using improved binary search technique. Floor value is the largest element smaller than equal to x, whereas ceil value is the smallest element greater than equal to x.

Improved Binary Search uses less number of comparisons in total as that in case of normal binary search technique. In normal binary search we use two comparisons per iteration except the final one when element is found if any. So theoretically logN + 1 comparisons.

In this version of comparison we depend only one comparison inside the loop. We need one more comparison to trace search status.

Examples:

Input: arr[] = {1, 3, 4, 7, 9, 13, 18, 23}, x = 14
Output: floor value - 13, ceil value - 18

Input: arr[] = {4, 5, 7, 9, 10, 12, 15, 17}, x = 13
Output: floor value - 12, ceil value - 15

Below is the idea of implementation of above idea:

C++

// C++ program to find floor and ceil of given value
// in a sorted array
#include <bits/stdc++.h>
using namespace std;

// Function to calculate the floor value of key = 8 
// in the sorted array arr[]
int floorOfx(int arr[], int l, int r, int key)
{
    int m;
    // Only one comparison in the while loop
    while(r - l > 1)
    {
        m = l + (r - l)/2;
        
        if(arr[m] <= key)
           l = m;
        else
           r = m;
    }
    
    return arr[l];
}

// Function to calculate the ceil value of key = 8 
// in the sorted array arr[]
int ceilOfx(int arr[], int l, int r, int key)
{
    int m;
    
    // Only one comparison in the while loop
    while(r - l > 1)
    {
        m = l + (r - l)/2;
        
        if(arr[m] <= key)
           l = m;
        else
           r = m;
    }
    
    return arr[r];
}

// Driver code
int main()
{
    // Sorted array
    int arr[] = {1, 3, 4, 7, 9, 13, 18, 23};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    // Key whose floor and ceil are to be calculated
    int key = 8;
    
    cout << "Floor value: " << floorOfx(arr, 0, n-1, key) << endl;
    cout << "Ceil value: " << ceilOfx(arr, 0, n-1, key) << endl;
}

Java

// Java program to find floor and ceil of a given value
// in a sorted array
import java.util.*;

public class Cplusplus
{
    // Function to calculate the floor value of key = 8
    // in the sorted array arr[]
    public static int floorOfx(int arr[], int l, int r, int key)
    {
        int m;
        // Only one comparison in the while loop
        while (r - l > 1)
        {
            m = l + (r - l) / 2;

            if (arr[m] <= key)
                l = m;
            else
                r = m;
        }

        return arr[l];
    }

    // Function to calculate the ceil value of key = 8
    // in the sorted array arr[]
    public static int ceilOfx(int arr[], int l, int r, int key)
    {
        int m;

        // Only one comparison in the while loop
        while (r - l > 1)
        {
            m = l + (r - l) / 2;

            if (arr[m] <= key)
                l = m;
            else
                r = m;
        }

        return arr[r];
    }

    // Driver code
    public static void main(String[] args)
    {
        // Sorted array
        int arr[] = { 1, 3, 4, 7, 9, 13, 18, 23 };
        int n = arr.length;

        // Key whose floor and ceil are to be calculated
        int x = 8;

        System.out.println("Floor value: " + floorOfx(arr, 0, n - 1, x));
        System.out.println("Ceil value: " + ceilOfx(arr, 0, n - 1, x));
    }
}

Output:

Floor value: 7
Ceil vaue: 9

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

C++

Java

Similar Reads