Floor and Ceiling in a sorted array | GeeksforGeeks

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.

For example, let the input array be {1, 2, 8, 10, 10, 12, 19}
For x = 0:    floor doesn't exist in array,  ceil  = 1
For x = 5:    floor  = 2,  ceil  = 8

Method 2 (Binary Search)

int ceilSearch(int arr[], int low, int high, int x)

{

  int mid;    

  /* If x is smaller than or equal to the first element,

    then return the first element */

  if(x <= arr[low])

    return low; 

  /* If x is greater than the last element, then return -1 */

  if(x > arr[high])

    return -1;  

  /* get the index of middle element of arr[low..high]*/

  mid = (low + high)/2;  /* low + (high - low)/2 */

  /* If x is same as middle element, then return mid */

  if(arr[mid] == x)

    return mid;

  /* If x is greater than arr[mid], then either arr[mid + 1]

    is ceiling of x or ceiling lies in arr[mid+1...high] */ 

  else if(arr[mid] < x)

  {

    if(mid + 1 <= high && x <= arr[mid+1])

      return mid + 1;

    else

      return ceilSearch(arr, mid+1, high, x);

  }

  /* If x is smaller than arr[mid], then either arr[mid] 

     is ceiling of x or ceiling lies in arr[mid-1...high] */   

  else

  {

    if(mid - 1 >= low && x > arr[mid-1])

      return mid;

    else    

      return ceilSearch(arr, low, mid - 1, x);

  }

}

Method 1 (Linear Search)
1) If x is smaller than or equal to the first element in array then return 0(index of first element)
2) Else Linearly search for an index i such that x lies between arr[i] and arr[i+1].
3) If we do not find an index i in step 2, then return -1

http://www.zrzahid.com/floor-and-ceiling-of-key-in-sorted-array-search-min-diff/

 //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.

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);
 }
}

Read full article from Floor and Ceiling in a sorted array | GeeksforGeeks