Floor and Ceil in Sorted Array in DSA C#

Mental Model

Floor is the biggest number less than or equal to the target. Ceil is the smallest number greater than or equal to the target. Both can be found quickly in a sorted list by checking middle points.

Analogy: Imagine a number line with houses sorted by their address. Floor is the closest house to the left or at your address. Ceil is the closest house to the right or at your address.

Sorted Array: [1] -> [3] -> [5] -> [7] -> [9] -> null
Target: 6
Floor: 5 (closest left)
Ceil: 7 (closest right)

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9], target: 6

Goal: Find floor and ceil values for target 6 in the sorted array

Step 1: Start binary search with low=0, high=4

[1] -> [3] -> [5] -> [7] -> [9] -> null, target=6, low=0, high=4

Why: We begin searching the whole array to find floor and ceil

Step 2: Calculate mid=2, value=5; 5 < 6, so floor candidate updated to 5, move low to mid+1=3

[1] -> [3] -> [5] -> [7] -> [9] -> null, floor=5, low=3, high=4

Why: 5 is less than target, so it can be floor; search right side for closer values

Step 3: Calculate mid=3, value=7; 7 > 6, so ceil candidate updated to 7, move high to mid-1=2

[1] -> [3] -> [5] -> [7] -> [9] -> null, floor=5, ceil=7, low=3, high=2

Why: 7 is greater than target, so it can be ceil; search left side for closer values

Result:

Floor: 5, Ceil: 7

Annotated Code

DSA C#

using System;

class FloorCeilFinder
{
    public static (int?, int?) FindFloorAndCeil(int[] arr, int target)
    {
        int low = 0, high = arr.Length - 1;
        int? floor = null, ceil = null;

        while (low <= high)
        {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target)
            {
                // Exact match is both floor and ceil
                return (arr[mid], arr[mid]);
            }
            else if (arr[mid] < target)
            {
                floor = arr[mid];
                low = mid + 1; // search right side
            }
            else
            {
                ceil = arr[mid];
                high = mid - 1; // search left side
            }
        }

        return (floor, ceil);
    }

    static void Main()
    {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 6;
        var (floor, ceil) = FindFloorAndCeil(arr, target);
        Console.WriteLine($"Floor: {(floor.HasValue ? floor.Value.ToString() : "null")}");
        Console.WriteLine($"Ceil: {(ceil.HasValue ? ceil.Value.ToString() : "null")}");
    }
}

while (low <= high)

loop to narrow search range until low passes high

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

calculate middle index to check value

if (arr[mid] == target)

check if exact match found, then floor and ceil are target

else if (arr[mid] < target)

update floor candidate and move search to right side

else

update ceil candidate and move search to left side

Output

Floor: 5

Ceil: 7

Complexity Analysis

Time: O(log n) because binary search halves the search space each step

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Linear search would be O(n) by checking each element; binary search is faster for sorted arrays

Edge Cases

target smaller than all elements

floor is null, ceil is the smallest element

DSA C#

return (floor, ceil);

target larger than all elements

floor is the largest element, ceil is null

DSA C#

return (floor, ceil);

target exactly matches an element

floor and ceil both equal target

DSA C#

if (arr[mid] == target) { return (arr[mid], arr[mid]); }

When to Use This Pattern

When you need to find closest smaller or larger values in a sorted list quickly, use binary search to find floor and ceil efficiently.

Common Mistakes

Mistake: Not updating floor or ceil candidates correctly when moving search boundaries
Fix: Update floor when arr[mid] < target and update ceil when arr[mid] > target before changing low or high

Mistake: Using linear search instead of binary search on sorted array
Fix: Use binary search to reduce time complexity from O(n) to O(log n)

Summary

Finds the closest smaller or equal (floor) and closest larger or equal (ceil) values to a target in a sorted array.

Use when you want quick nearest value lookups in sorted data.

The key is to use binary search to narrow down candidates for floor and ceil efficiently.

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