Floor and Ceil in Sorted Array in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find floor and ceil of 5 in the array

Given the sorted array int[] arr = {1, 2, 4, 6, 8, 10};, what is the output of the floor and ceil values for key = 5?

DSA C#

int Floor(int[] arr, int key) {
    int left = 0, right = arr.Length - 1;
    int floor = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) return arr[mid];
        if (arr[mid] < key) {
            floor = arr[mid];
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return floor;
}

int Ceil(int[] arr, int key) {
    int left = 0, right = arr.Length - 1;
    int ceil = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) return arr[mid];
        if (arr[mid] > key) {
            ceil = arr[mid];
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ceil;
}

int[] arr = {1, 2, 4, 6, 8, 10};
int key = 5;
int floorValue = Floor(arr, key);
int ceilValue = Ceil(arr, key);
Console.WriteLine($"Floor: {floorValue}, Ceil: {ceilValue}");

A Floor: 4, Ceil: 6

B Floor: 5, Ceil: 5

C Floor: -1, Ceil: -1

D Floor: 6, Ceil: 8

💡 Hint

Remember floor is the greatest element less than or equal to key, ceil is the smallest element greater than or equal to key.

The floor of 5 is 4 because 4 is the greatest number less than 5 in the array. The ceil of 5 is 6 because 6 is the smallest number greater than 5 in the array.

❓ Predict Output

intermediate

Floor and Ceil for key smaller than all elements

What will be the output of floor and ceil for key = 0 in the sorted array int[] arr = {3, 5, 7, 9};?

DSA C#

int Floor(int[] arr, int key) {
    int left = 0, right = arr.Length - 1;
    int floor = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) return arr[mid];
        if (arr[mid] < key) {
            floor = arr[mid];
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return floor;
}

int Ceil(int[] arr, int key) {
    int left = 0, right = arr.Length - 1;
    int ceil = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) return arr[mid];
        if (arr[mid] > key) {
            ceil = arr[mid];
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ceil;
}

int[] arr = {3, 5, 7, 9};
int key = 0;
int floorValue = Floor(arr, key);
int ceilValue = Ceil(arr, key);
Console.WriteLine($"Floor: {floorValue}, Ceil: {ceilValue}");

A Floor: -1, Ceil: -1

B Floor: 3, Ceil: 3

C Floor: -1, Ceil: 3

D Floor: 0, Ceil: 3

💡 Hint

If key is smaller than all elements, floor should be -1 (no floor), ceil should be the smallest element.

Since 0 is smaller than all elements, floor does not exist (-1). The ceil is the smallest element 3.

🔧 Debug

advanced

Identify the bug in floor function

Consider the following floor function for a sorted array. What is the bug that causes incorrect floor value for some inputs?

int Floor(int[] arr, int key) {
    int left = 0, right = arr.Length - 1;
    int floor = -1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) return arr[mid];
        if (arr[mid] < key) {
            floor = arr[mid];
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return floor;
}

A The floor variable should be initialized to 0 instead of -1.

B The loop condition should be 'left <= right' instead of 'left < right'.

C The mid calculation should be 'mid = (left + right) / 2 + 1'.

D The function should return 'arr[left]' instead of 'floor' at the end.

💡 Hint

Check if the loop covers all elements including when left equals right.

Using 'left < right' skips the case when left == right, potentially missing the correct floor. Changing to 'left <= right' ensures all elements are checked.

🧠 Conceptual

advanced

Floor and Ceil when key is present in array

If the key is present in the sorted array, what will be the floor and ceil values returned by the standard binary search based floor and ceil functions?

A Floor will be the element before the key, ceil will be the element after the key.

B Floor will be the key, ceil will be -1.

C Floor will be -1, ceil will be the key.

D Both floor and ceil will be equal to the key itself.

💡 Hint

Think about what floor and ceil mean when the key exists exactly in the array.

If the key is found, both floor and ceil are the key itself because floor is the greatest element less than or equal to key, and ceil is the smallest element greater than or equal to key.

❓ Predict Output

expert

Floor and Ceil for large array with duplicates

Given the sorted array int[] arr = {1, 2, 2, 2, 3, 4, 5, 5, 6};, what is the output of floor and ceil for key = 2?

DSA C#

int Floor(int[] arr, int key) {
    int left = 0, right = arr.Length - 1;
    int floor = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) return arr[mid];
        if (arr[mid] < key) {
            floor = arr[mid];
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return floor;
}

int Ceil(int[] arr, int key) {
    int left = 0, right = arr.Length - 1;
    int ceil = -1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == key) return arr[mid];
        if (arr[mid] > key) {
            ceil = arr[mid];
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ceil;
}

int[] arr = {1, 2, 2, 2, 3, 4, 5, 5, 6};
int key = 2;
int floorValue = Floor(arr, key);
int ceilValue = Ceil(arr, key);
Console.WriteLine($"Floor: {floorValue}, Ceil: {ceilValue}");

A Floor: 2, Ceil: 2

B Floor: 1, Ceil: 3

C Floor: 2, Ceil: 3

D Floor: 1, Ceil: 2

💡 Hint

When key is present multiple times, floor and ceil should return the key itself.

Since 2 is present in the array, both floor and ceil return 2 regardless of duplicates.

Practice

1. What does the floor of a number mean in a sorted array context?

easy

A. The average of all elements less than the number

B. The smallest element greater than or equal to the number

C. The smallest element strictly less than the number

D. The greatest element less than or equal to the number

Solution

1. Step 1: Understand floor definition in sorted array

   The floor of a number is the greatest element in the array that is less than or equal to that number.

2. Step 2: Compare options with definition

   The greatest element less than or equal to the number matches the definition exactly. Options A, B, and D do not match the floor concept.

3. Final Answer:

   The greatest element less than or equal to the number -> Option D

4. Quick Check:

   Floor = greatest ≤ number [OK]

Hint: Floor is always ≤ the target number [OK]

Common Mistakes:

• Confusing floor with ceil
• Thinking floor is strictly less than the number
• Mixing floor with average or median

2. Which of the following C# method signatures correctly represents a function to find the floor in a sorted integer array (with array as first parameter)?

easy

A. void FindFloor(int[] arr, int target)

B. int FindFloor(int[] arr, int target)

C. int FindFloor(int target, int[] arr)

D. int FindFloor(List<int> arr, string target)

Solution

1. Step 1: Check method return type and parameters

   The function should return an integer (the floor value) and accept an integer array and an integer target.

2. Step 2: Validate each option

   int FindFloor(int[] arr, int target) matches the correct signature: returns int, takes int[] and int. void FindFloor(int[] arr, int target) returns void, so no result. int FindFloor(int target, int[] arr) swaps parameters order (less common but possible). int FindFloor(List<int> arr, string target) uses wrong types (List<int> and string target).

3. Final Answer:

   int FindFloor(int[] arr, int target) -> Option B

4. Quick Check:

   Return int, params (int[], int) [OK]

Hint: Floor function returns int and takes int array, int target [OK]

Common Mistakes:

• Using void return type
• Swapping parameter order incorrectly
• Using wrong parameter types

3. What is the output of the following C# code?

int[] arr = {1, 3, 5, 7, 9};
int target = 6;
int floor = -1;
int left = 0, right = arr.Length - 1;
while (left <= right) {
  int mid = left + (right - left) / 2;
  if (arr[mid] == target) {
    floor = arr[mid];
    break;
  } else if (arr[mid] < target) {
    floor = arr[mid];
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}
Console.WriteLine(floor);

medium

A. 5

B. 7

C. 6

D. -1

Solution

1. Step 1: Trace binary search for floor of 6

   Initial array: [1,3,5,7,9]. Target=6. Start left=0, right=4, floor=-1.
   mid=2 (arr[2]=5) < 6, floor=5, left=3.
   mid=3 (arr[3]=7) > 6, right=2.
   Loop ends as left > right.

2. Step 2: Final floor value

   Floor is 5, the greatest element ≤ 6.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Floor(6) in [1,3,5,7,9] = 5 [OK]

Hint: Floor is last smaller or equal element found in binary search [OK]

Common Mistakes:

• Returning 7 instead of 5
• Confusing floor with ceil
• Not updating floor inside loop

4. The following code is intended to find the ceil of a target in a sorted array but has a bug. What is the bug?

int Ceil(int[] arr, int target) {
  int left = 0, right = arr.Length - 1;
  int ceil = -1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) {
      return arr[mid];
    } else if (arr[mid] > target) {
      ceil = arr[mid];
      right = mid + 1;
    } else {
      left = mid + 1;
    }
  }
  return ceil;
}

medium

A. The function should return -1 if no ceil found

B. left should be updated to mid - 1, not mid + 1

C. right should be updated to mid - 1, not mid + 1

D. ceil should be initialized to 0, not -1

Solution

1. Step 1: Analyze right pointer update in binary search

   When arr[mid] > target, we want to search left half, so right should move to mid - 1, not mid + 1.

2. Step 2: Identify impact of wrong update

   Using right = mid + 1 moves right pointer incorrectly, causing infinite loop or wrong result.

3. Final Answer:

   right should be updated to mid - 1, not mid + 1 -> Option C

4. Quick Check:

   Correct binary search halves pointers [OK]

Hint: When arr[mid] > target, move right to mid - 1 [OK]

Common Mistakes:

• Updating right pointer incorrectly
• Confusing ceil with floor logic
• Not returning correct default value

5. Given a sorted array arr = {2, 4, 6, 8, 10} and a target 5, write a C# method to return both floor and ceil values as a tuple. What should the method return?

medium

A. (4, 6)

B. (2, 4)

C. (5, 5)

D. (-1, -1)

Solution

1. Step 1: Identify floor and ceil for target 5 in array

   Array: [2,4,6,8,10]. Floor is greatest ≤ 5, which is 4. Ceil is smallest ≥ 5, which is 6.

2. Step 2: Confirm tuple return

   The method should return (floor, ceil) = (4, 6).

3. Final Answer:

   (4, 6) -> Option A

4. Quick Check:

   Floor=4, Ceil=6 for target 5 [OK]

Hint: Floor ≤ target, Ceil ≥ target; pick closest values [OK]

Common Mistakes:

• Returning target itself when not in array
• Swapping floor and ceil values
• Returning -1 when values exist