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)