Floor and Ceil in Sorted Array in DSA Javascript - Execution Trace

Concept Flow - Floor and Ceil in Sorted Array

Start with sorted array and target

↓

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

↓

While low <= high

↓

Calculate mid = Math.floor((low+high)/2)

↓

Compare array[mid

↓

low=mid+1

↓

Loop until low > high

↓

Return floor and ceil based on final low and high

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

Execution Sample

DSA Javascript

function floorAndCeil(arr, target) {
  let low = 0, high = arr.length - 1;
  let floor = -1, ceil = -1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return { floor: arr[mid], ceil: arr[mid] };
    else if (arr[mid] < target) {
      floor = arr[mid];
      low = mid + 1;
    } else {
      ceil = arr[mid];
      high = mid - 1;
    }
  }
  return { floor, ceil };
}

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? 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 is 6, ceil is 8

Variable Tracker

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

Key Moments - 3 Insights

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

Because arr[mid] is less than target and could be the closest smaller value. See step 2 and 3 where floor updates to 6.

Why does the loop stop when low > high?

Because the search space is empty, meaning we have found the closest floor and ceil. See step 8 where low=4 and high=3.

What if target equals arr[mid]?

We return floor and ceil as that exact value immediately. This is shown in the code line inside the loop checking arr[mid] === target.

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 row for step 4 in execution_table.

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

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Look at the 'Comparison' column and 'Exit loop' row in execution_table.

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

A floor=8, ceil=10

B floor=10, ceil=10

C floor=10, ceil=12

D floor=6, ceil=8

💡 Hint

Recall the code returns exact match floor and ceil immediately if arr[mid] === target.

Concept Snapshot

Floor and Ceil in Sorted Array:
- Use binary search with low=0, high=length-1
- Calculate mid = Math.floor((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
- Return floor and ceil found

Full Transcript

This concept finds the floor and ceil of a target number 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, we return that value as both floor and ceil. If arr[mid] is less than target, we update floor and move low up. If arr[mid] is greater, we update ceil and move high down. We repeat until low passes high, then return the last floor and ceil values found. The execution table shows step-by-step how low, high, mid, floor, and ceil change. Key moments clarify why floor updates when arr[mid] < target, why the loop stops when low > high, and what happens on exact match. The visual quiz tests understanding of these steps and outcomes.