Floor and Ceil in Sorted Array in DSA C# - Execution Trace

Concept Flow - Floor and Ceil in Sorted Array

Start

↓

Input: Sorted Array, Target

↓

Initialize low=0, high=array.length-1

↓

While low <= high

↓

mid = (low+high)/2

↓

Compare array[mid

↓

array[mid

↓

Floor = Ceil = array[mid

↓

End

↓

array[mid

↓

Floor = array[mid

↓

low = mid + 1

↓

Ceil = array[mid

↓

high = mid - 1

↓

Loop ends

↓

Return Floor and Ceil

↓

End

This flow shows how binary search is used to find floor and ceil values by adjusting low and high pointers and updating floor and ceil candidates.

Execution Sample

DSA C#

int floor = -1;
int ceil = -1;
int low = 0, high = arr.Length - 1;
while (low <= high) {
  int mid = (low + high) / 2;
  if (arr[mid] == target) return (arr[mid], arr[mid]);
  else if (arr[mid] < target) { floor = arr[mid]; low = mid + 1; }
  else { ceil = arr[mid]; high = mid - 1; }
}
return (floor, ceil);

Find floor and ceil of target in sorted array using binary search.

Execution Table

Step	Operation	low	high	mid	Comparison	Floor	Ceil	Visual State
1	Initialize	0	6	-	-	-1	-1	[1, 2, 4, 6, 8, 10, 12]
2	Calculate mid	0	6	3	arr[3]=6 < 7	6	-1	[1, 2, 4, 6, 8, 10, 12]
3	Update low	4	6	-	-	6	-1	[1, 2, 4, 6, 8, 10, 12]
4	Calculate mid	4	6	5	arr[5]=10 > 7	6	10	[1, 2, 4, 6, 8, 10, 12]
5	Update high	4	4	-	-	6	10	[1, 2, 4, 6, 8, 10, 12]
6	Calculate mid	4	4	4	arr[4]=8 > 7	6	8	[1, 2, 4, 6, 8, 10, 12]
7	Update high	4	3	-	-	6	8	[1, 2, 4, 6, 8, 10, 12]
8	Exit loop	4	3	-	low > high	6	8	[1, 2, 4, 6, 8, 10, 12]

💡 Loop ends because low (4) > high (3), floor=6, ceil=8 found.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
low	0	0	4	4	4	4	4	4
high	6	6	6	6	4	4	3	3
mid	-	3	-	5	-	4	-	-
floor	-1	6	6	6	6	6	6	6
ceil	-1	-1	-1	10	10	8	8	8

Key Moments - 3 Insights

Why do we update floor only when arr[mid] < target?

Because floor is the greatest value less than or equal to target. When arr[mid] < target, arr[mid] is a candidate for floor. See execution_table rows 2 and 3 where floor updates to 6.

Why do we update ceil only when arr[mid] > target?

Because ceil is the smallest value greater than or equal to target. When arr[mid] > target, arr[mid] is a candidate for ceil. See execution_table rows 4 and 6 where ceil updates to 10 then 8.

What happens if target equals an element in the array?

The function returns that element as both floor and ceil immediately. This is shown in the concept flow at the decision point where arr[mid] == target.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what are the values of floor and ceil?

A floor=6, ceil=10

B floor=10, ceil=6

C floor=-1, ceil=10

D floor=6, ceil=-1

💡 Hint

Check the Floor and Ceil columns in execution_table row with Step 4.

At which step does the loop condition become false?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Look at the exit_note and the Condition column in execution_table row 8.

If the target was 10 instead of 7, what would the floor and ceil be at the end?

A floor=8, ceil=10

B floor=10, ceil=10

C floor=10, ceil=12

D floor=7, ceil=10

💡 Hint

Recall from concept_flow that if arr[mid] == target, floor and ceil both equal that element.

Concept Snapshot

Floor and Ceil in Sorted Array:
- Use binary search with low and high pointers.
- If arr[mid] == target, floor = ceil = arr[mid].
- If arr[mid] < target, update floor and move low up.
- If arr[mid] > target, update ceil and move high down.
- Loop ends when low > high, return floor and ceil.
- Floor is greatest <= target, Ceil is smallest >= target.

Full Transcript

This concept shows how to find floor and ceil values of a target in a sorted array using binary search. We start with low at 0 and high at the last index. We calculate mid and compare arr[mid] with target. If equal, we return arr[mid] as both floor and ceil. If arr[mid] is less than target, we update floor to arr[mid] and move low to mid + 1. If arr[mid] is greater than target, we update ceil to arr[mid] and move high to mid - 1. We repeat until low exceeds high. The final floor and ceil are returned. This method efficiently finds the closest smaller and larger values around the target in a sorted list.

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