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

↓

Set low = 0, high = n-1

↓

While low <= high

↓

Calculate mid = (low + high) / 2

↓

Compare arr[mid

↓

low = mid+1

↓

Loop until low > high

↓

Return floor and ceil values

We use binary search to find floor and ceil by narrowing search space until low passes high.

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 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	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	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	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 when 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 not ceil?

Because floor is the greatest value less than or equal to target. When arr[mid] < target, arr[mid] can be floor, so we update floor and move low up to search higher values (see Step 2 and 3). Ceil is updated only when arr[mid] > target.

Why does the loop stop when low > high?

The loop stops when low passes high because it means all elements have been checked and no exact match found. At this point, floor and ceil hold the closest smaller and larger values respectively (see Step 8).

What if target is smaller than all elements?

Floor remains -1 (no smaller or equal element), ceil updates to the smallest element greater than target (see variable ceil in execution_table rows 4 and 6).

Visual Quiz - 3 Questions

Look at the execution table, what is the value of floor after Step 4?

A 6

B 10

C -1

D 8

💡 Hint

Check the 'Floor' column in the execution_table row for Step 4.

At which step does the loop condition become false?

A Step 6

B Step 8

C Step 7

D Step 5

💡 Hint

Look at the 'Operation' and 'low' and 'high' values in the execution_table rows to find when low > high.

If the target was 13 (greater than all elements), what would be the final floor value?

A 13

B -1

C 12

D 10

💡 Hint

Floor is the greatest element less than or equal to target; check variable_tracker for floor updates.

Concept Snapshot

Floor and Ceil in Sorted Array:
- Use binary search with low=0, high=n-1
- Calculate mid = (low+high)/2 each step
- 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
- Floor = greatest <= target, Ceil = smallest >= target

Full Transcript

This concept finds the floor and ceil of a target number in a sorted array using binary search. We start with low at 0 and high at the last index. Each step calculates mid as the middle index. If the middle element equals the target, both floor and ceil are that element. If the middle element is less than the target, floor updates to that element and low moves up to search higher values. If the middle element is greater than the target, ceil updates to that element and high moves down to search lower values. The loop continues until low passes high, meaning all elements are checked. At the end, floor holds the greatest element less than or equal to the target, and ceil holds the smallest element greater than or equal to the target. This method efficiently finds floor and ceil in O(log n) time.

Practice

1. What is the floor of a number in a sorted array?

easy

A. The smallest element strictly less than the number

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

C. The average of all elements 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 the given number.

2. Step 2: Compare options with definition

   The greatest element less than or equal to the number matches the definition exactly, others describe ceil or incorrect concepts.

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 ≤ number, pick greatest such element [OK]

Common Mistakes:

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

2. Which of the following is the correct C syntax to find the middle index in binary search for array of size n?

easy

A. int mid = (0 + n) / 2;

B. int mid = 0 + n - 1 / 2;

C. int mid = (0 + (n - 1)) >> 1;

D. int mid = n / 2;

Solution

1. Step 1: Understand middle index calculation in binary search

   For array indices 0 to n-1, middle is (0 + n-1) / 2 or equivalent.

2. Step 2: Analyze options for correct syntax and efficiency

   int mid = (0 + (n - 1)) >> 1; uses bitwise right shift for division by 2, which is efficient and correct for integer mid calculation.

3. Final Answer:

   int mid = (0 + (n - 1)) >> 1; -> Option C

4. Quick Check:

   Mid = (start + end) >> 1 [OK]

Hint: Use (start + end) >> 1 for efficient mid calculation [OK]

Common Mistakes:

• Using n instead of n-1 as end index
• Forgetting parentheses causing wrong precedence
• Using floating division instead of integer

3. Given the sorted array arr = {1, 3, 5, 7, 9}, what is the floor of 6?

medium

A. 7

B. 5

C. 6

D. -1

Solution

1. Step 1: Identify elements less than or equal to 6

   Elements ≤ 6 are 1, 3, 5.

2. Step 2: Find greatest among these

   The greatest element ≤ 6 is 5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Floor(6) = 5 [OK]

Hint: Floor is largest ≤ target in sorted array [OK]

Common Mistakes:

• Choosing 7 which is greater than 6
• Assuming floor equals the number if not present
• Returning -1 incorrectly when floor exists

4. Consider this code snippet to find ceil in a sorted array int ceil = -1; for(int i=0; i= x) { ceil = arr[i]; break; } }. What is the main issue?

medium

A. It may return wrong value if array is not sorted

B. It does not handle empty array

C. It returns first element ≥ x, which is correct for ceil

D. It finds floor instead of ceil

Solution

1. Step 1: Understand the code logic

   The code returns the first element in array ≥ x, which is correct if array is sorted.

2. Step 2: Identify assumptions and issues

   If array is not sorted, first element ≥ x may not be the smallest such element, so ceil is incorrect.

3. Final Answer:

   It may return wrong value if array is not sorted -> Option A

4. Quick Check:

   Ceil requires sorted array for correctness [OK]

Hint: Ceil logic needs sorted array to work correctly [OK]

Common Mistakes:

• Ignoring array sorting requirement
• Confusing ceil with floor
• Not checking for empty array before loop

5. You have a sorted array arr = {2, 4, 6, 8, 10}. If you want to find the ceil of 11 using binary search, what should be the returned value?

hard

A. -1

B. 11

C. 10

D. Error

Solution

1. Step 1: Understand ceil definition and array elements

   Ceil is smallest element ≥ target. Here, target is 11, which is greater than all elements.

2. Step 2: Check if any element ≥ 11 exists

   No element in array ≥ 11, so ceil does not exist, return -1.

3. Final Answer:

   -1 -> Option A

4. Quick Check:

   No element ≥ 11 means ceil = -1 [OK]

Hint: If target > max element, ceil is -1 (not found) [OK]

Common Mistakes:

• Returning last element as ceil incorrectly
• Returning target itself if not found
• Not handling no ceil case properly