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;
} elseif (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
Test your understanding
Look at the execution_table, what is the value of floor after step 4?
A10
B6
C-1
D8
💡 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?
AStep 6
BStep 7
CStep 8
DStep 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?
Afloor=10, ceil=10
Bfloor=10, ceil=12
Cfloor=8, ceil=10
Dfloor=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.