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

Concept Flow - Floor and Ceil in Sorted Array

Start with sorted array and target

↓

Initialize low=0, high=n-1

↓

While low <= high

↓

Calculate mid = (low+high)/2

↓

Compare arr[mid

↓

Equal

↓

Floor=arr[mid

↓

Repeat until low > high

↓

Return Floor and Ceil values

This flow shows how binary search narrows down to find floor and ceil values for a target in a sorted array.

Execution Sample

DSA C++

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

This code finds floor and ceil of target in a sorted array using binary search.

Execution Table

Step	Operation	low	high	mid	arr[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	6	6 < 7? Yes	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	10	10 > 7? Yes	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	8	8 > 7? Yes	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 4	After Step 6	Final
low	0	4	4	4	4
high	6	6	4	3	3
mid	-	3	5	4	-
floor	-1	6	6	6	6
ceil	-1	-1	10	8	8

Key Moments - 3 Insights

Why do we update floor when arr[mid] < target but update ceil when arr[mid] > target?

Because floor is the greatest value less than or equal to target, so when arr[mid] < target, arr[mid] is a candidate floor. Similarly, ceil is the smallest value greater than or equal to target, so when arr[mid] > target, arr[mid] is a candidate ceil. This is shown in steps 2, 4, and 6 in the execution_table.

Why does the loop stop when low > high?

The loop stops when low passes high because all possible positions have been checked. At this point, floor and ceil hold the closest values to the target. This is shown at step 8 in the execution_table.

What if the target is exactly equal to arr[mid]?

If arr[mid] equals target, both floor and ceil are set to arr[mid], and the search can stop immediately. This case is handled in the code but not shown in this example since target=7 is not in the array.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of floor after step 4?

A 10

B 6

C -1

D 8

💡 Hint

Check the 'Floor' column at step 4 in the execution_table.

At which step does the condition low > high become true, ending the loop?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Look at the 'Exit loop' row and the 'low' and 'high' values in the execution_table.

If the target was 10, what would floor and ceil be after the loop?

A floor=10, ceil=10

B floor=10, ceil=12

C floor=8, ceil=10

D floor=6, ceil=8

💡 Hint

When target equals an element in the array, floor and ceil are both that element.

Concept Snapshot

Floor and Ceil in Sorted Array:
- Use binary search with low=0, high=n-1
- Calculate mid = (low+high)/2
- If arr[mid] == target, floor=ceil=arr[mid]
- If arr[mid] < target, floor=arr[mid], low=mid+1
- If arr[mid] > target, ceil=arr[mid], high=mid-1
- Loop until low > high
- Result: floor and ceil closest to 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 and high pointers at the array ends. We calculate mid and compare arr[mid] with target. If equal, floor and ceil are arr[mid]. If arr[mid] is less, update floor and move low up. If arr[mid] is more, update ceil and move high down. Repeat until low passes high. The final floor and ceil are the closest values to the target. The execution table traces these steps with variable values and array state.

Practice

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

easy

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

B. The smallest element greater than the number

C. The average of all elements less than the number

D. The smallest element less than 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 the given number.

2. Step 2: Compare options with definition

   The greatest element less than or equal to the number matches the definition exactly. Other options describe different concepts.

3. Final Answer:

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

4. Quick Check:

   Floor = greatest ≤ number [OK]

Hint: Floor is always ≤ number, pick greatest such element [OK]

Common Mistakes:

• Confusing floor with ceil
• Choosing smallest element greater than number
• Thinking floor is average or exact match only

2. Which of the following is the correct C++ function signature to find the floor of a number in a sorted array?

easy

A. int findFloor(int arr[], int n, int x);

B. void findFloor(int arr[], int n, int x);

C. int findFloor(int arr, int n, int x);

D. int findFloor(int arr[], int x);

Solution

1. Step 1: Analyze function parameters

   The function needs the array, its size, and the target number to find floor.

2. Step 2: Check each option's signature

   int findFloor(int arr[], int n, int x); correctly uses array pointer, size, and target number. void findFloor(int arr[], int n, int x); returns void which is incorrect. int findFloor(int arr, int n, int x); uses int arr instead of array. int findFloor(int arr[], int x); misses size parameter.

3. Final Answer:

   int findFloor(int arr[], int n, int x); -> Option A

4. Quick Check:

   Correct signature includes array, size, target [OK]

Hint: Function needs array, size, and target number [OK]

Common Mistakes:

• Omitting array size parameter
• Using wrong array type
• Returning void instead of int

3. What is the output of the following code snippet?

int arr[] = {1, 3, 5, 7, 9};
int n = 5;
int x = 6;
int floor = -1;
for (int i = 0; i < n; i++) {
  if (arr[i] <= x) floor = arr[i];
  else break;
}
std::cout << floor;

medium

A. 6

B. 7

C. 5

D. -1

Solution

1. Step 1: Trace the loop and condition

   Loop checks each element ≤ 6. Elements 1, 3, 5 satisfy condition, floor updates to 5. When arr[i] = 7, condition fails and loop breaks.

2. Step 2: Determine final floor value

   Floor remains 5 after loop ends.

3. Final Answer:

   5 -> Option C

4. Quick Check:

   Floor of 6 in array = 5 [OK]

Hint: Floor is last element ≤ target before break [OK]

Common Mistakes:

• Choosing 6 which is not in array
• Choosing 7 which is > 6
• Not updating floor correctly

4. Find the error in the following code to find the ceil of a number in a sorted array:

int findCeil(int arr[], int n, int x) {
  int ceil = -1;
  for (int i = 0; i < n; i++) {
    if (arr[i] >= x) {
      ceil = arr[i];
    }
  }
  return ceil;
}

medium

A. It uses wrong comparison operator

B. It returns -1 even if ceil exists

C. It should return floor instead of ceil

D. It does not return the smallest element ≥ x

Solution

1. Step 1: Understand the loop logic

   The loop updates ceil whenever arr[i] ≥ x, but does not stop or check for smallest such element.

2. Step 2: Identify the error

   Because it keeps updating, it ends with the last element ≥ x, not the smallest. It should break or track minimum.

3. Final Answer:

   It does not return the smallest element ≥ x -> Option D

4. Quick Check:

   Ceil = smallest ≥ x, code returns largest ≥ x [OK]

Hint: Ceil must be smallest ≥ target, not last found [OK]

Common Mistakes:

• Not breaking loop after first valid ceil
• Updating ceil without checking if smaller
• Confusing floor and ceil logic

5. Given a sorted array arr = {2, 4, 6, 8, 10}, what are the floor and ceil of x = 5? Choose the correct pair.

hard

A. Floor = 5, Ceil = 6

B. Floor = 4, Ceil = 6

C. Floor = 4, Ceil = 5

D. Floor = 6, Ceil = 8

Solution

1. Step 1: Find floor of 5 in array

   Floor is greatest element ≤ 5. Elements ≤ 5 are 2 and 4, greatest is 4.

2. Step 2: Find ceil of 5 in array

   Ceil is smallest element ≥ 5. Elements ≥ 5 are 6, 8, 10, smallest is 6.

3. Final Answer:

   Floor = 4, Ceil = 6 -> Option B

4. Quick Check:

   Floor ≤ 5 = 4, Ceil ≥ 5 = 6 [OK]

Hint: Floor ≤ x, Ceil ≥ x; pick closest elements [OK]

Common Mistakes:

• Assuming floor or ceil must equal x
• Choosing elements not in array
• Mixing floor and ceil values