Algorithms
Floor and Ceiling of a Key in Sorted Array – Search Min Diff Element
Given a sorted array and a value x, the ceiling of x is the smallest element in array greater than or equal to x, and the floor is the greatest element smaller than or equal to x. Assume than the array is sorted in non-decreasing order. Write efficient functions to find floor and ceiling of x.
O(lgn) solution using modified Binary Search
//largest element smaller than or equal to key
public static int binarySearchFloor(int A[], int l, int h, int key){
int mid = (l+h)/2;
if(A[h] <= key){
return h;
}
if(A[l] > key ){
return -1;
}
if(A[mid] == key){
return mid;
}
//mid is greater than key, so floor is either mid-1 or it exists in A[l..mid-1]
else if(A[mid] > key){
if(mid-1 >= l && A[mid-1] <= key){
return mid-1;
}
else{
return binarySearchFloor(A, l, mid-1, key);
}
}
//mid is less than key, so floor is either mid or it exists in A[mid+1....h]
else{
if(mid+1 <= h && A[mid+1] > key){
return mid;
}
else{
return binarySearchFloor(A, mid+1, h, key);
}
}
}
//smallest element greater than or equal to key
public static int binarySearchCeiling(int A[], int l, int h, int key){
int mid = (l+h)/2;
if(A[l] >= key){
return l;
}
if(A[h] < key ){
return -1;
}
if(A[mid] == key){
return mid;
}
//mid is greater than key, so either mid is the ceil or it exists in A[l..mid-1]
else if(A[mid] > key){
if(mid-1 >= l && A[mid-1] <= key){
return mid;
}
else{
return binarySearchCeiling(A, l, mid-1, key);
}
}
//mid is less than the key, so either mid+1 is the ceil or it exists in A[mid+1...h]
else{
if(mid + 1 <= h && A[mid+1] >= key){
return mid+1;
}
else{
return binarySearchCeiling(A, mid+1, h, key);
}
}
}
Search Min Diff Element
Given a sorted array and a number. Find the element in the array that has minimum difference with the given number.
For example, if A=[-1,0,3,3,5,6,8] then minDiff(A, 2) will be 3 at index 2. minDiff(A, 3) will be 3 at index 2.
We can modify the binary search to find minDiff element in O(lgn) time as follow –
int searchMinDiffElement ( int a[], int n, int start, int end)
{
int middle = (start+end)/2;
if (a[middle] == n)
return n;
if (a[middle] > n)
{
if(middle == start)
return a[middle];
if( abs(a[middle-1] - n) >= abs(a[middle] - n)
return a[middle];
searchMinDiffElement (a, n, start, middle-1);
}
else
{
if(middle == end)
return a[middle];
if( (abs[middle+1] - n) >= abs(a[middle] - n))
return a[middle];
searchMinDiffElement (a, n, start, middle+1);
}
}