Floor and Ceil in Sorted Array in DSA Go - 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

↓

Update floor

↓

Move low=mid+1

↓

Repeat loop

↓

Return floor and ceil values

We use binary search to find floor and ceil by narrowing the search range and updating floor or ceil pointers based on comparisons.

Execution Sample

DSA Go

arr := []int{1, 3, 5, 7, 9}
target := 6
floor, ceil := -1, -1
low, high := 0, len(arr)-1
for low <= high {
  mid := (low + high) / 2
  if arr[mid] == target {
    floor, ceil = arr[mid], 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 6 in a sorted array using binary search.

Execution Table

Step	Operation	mid	arr[mid]	Comparison	floor	ceil	low	high	Visual State
1	Initialize	-	-	-	-1	-1	0	4	[1, 3, 5, 7, 9]
2	Calculate mid	2	5	5 < 6	5	-1	3	4	[1, 3, 5, 7, 9]
3	Calculate mid	3	7	7 > 6	5	7	3	2	[1, 3, 5, 7, 9]
4	Exit loop	-	-	low(3) > high(2)	5	7	3	2	[1, 3, 5, 7, 9]

💡 Loop ends because low (3) > high (2), floor is 5, ceil is 7

Variable Tracker

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

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 or equal value, so we save it as floor (see step 2 in execution_table).

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

Because arr[mid] is greater than target and could be the closest greater or equal value, so we save it as ceil (see step 3 in execution_table).

Why does the loop stop when low > high?

Because the search space is empty, meaning we have found the closest floor and ceil values (see step 4 in execution_table).

Visual Quiz - 3 Questions

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

A 5

B -1

C 7

D 3

💡 Hint

Check the 'floor' column in row for step 2 in execution_table.

At which step does the condition low <= high become false?

A Step 2

B Step 3

C Step 4

D Never

💡 Hint

Look at the 'low' and 'high' values in execution_table rows and see when low > high.

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

A floor=5, ceil=7

B floor=7, ceil=7

C floor=7, ceil=9

D floor=3, ceil=5

💡 Hint

If arr[mid] == target, floor and ceil both equal target (see code in execution_sample).

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], move low=mid+1
- If arr[mid] > target, ceil=arr[mid], move high=mid-1
- Loop ends when low > high, return floor and ceil

Full Transcript

We find floor and ceil in a sorted array by binary searching for the target. We keep track of floor as the largest value less than or equal to target, and ceil as the smallest value greater than or equal to target. At each step, we calculate mid and compare arr[mid] with target. If equal, floor and ceil are the same. If arr[mid] is less, update floor and move low up. If arr[mid] is greater, update ceil and move high down. The loop ends when low passes high, returning the closest floor and ceil values.