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

Concept Flow - Floor and Ceil in Sorted Array

Start

↓

Set low=0, high=n-1

↓

While low <= high

↓

Calculate mid = (low+high)//2

↓

Compare arr[mid

↓

arr[mid

↓

arr[mid

↓

arr[mid

↓

Repeat loop

↓

End: return floor and ceil

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

Execution Sample

DSA Python

arr = [1, 3, 5, 7, 9]
target = 6
floor = -1
ceil = -1
low, high = 0, len(arr)-1
while low <= high:
    mid = (low + high) // 2
    if arr[mid] == target:
        floor = ceil = arr[mid]
        break
    elif arr[mid] < target:
        floor = arr[mid]
        low = mid + 1
    else:
        ceil = arr[mid]
        high = mid - 1
print(floor, ceil)

Find floor and ceil of 6 in sorted array [1,3,5,7,9] using binary search.

Execution Table

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

💡 Loop ends because low (3) > high (2), floor=5 and ceil=7 found.

Variable Tracker

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

Key Moments - 3 Insights

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

Because arr[mid] is less than target, it can be a candidate for floor (largest smaller or equal), but ceil must be greater or equal, so we update floor only (see Step 2 in execution_table).

Why does the loop stop when low > high?

The search space is empty when low > high, meaning no exact match found and floor and ceil are the best candidates found so far (see Step 6 in execution_table).

What if target is smaller than all elements?

Floor remains -1 (no smaller element), ceil updates to the smallest element found during search (see ceil updates in execution_table).

Visual Quiz - 3 Questions

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

A 3

B 5

C -1

D 7

💡 Hint

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

At which step does the loop condition become false?

A Step 6

B Step 5

C Step 4

D Step 3

💡 Hint

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

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

A 9

B 10

C -1

D None

💡 Hint

Consider that ceil is the smallest element >= target; if none, it stays -1 as per variable_tracker.

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 ends when low > high
- Return floor and ceil (or -1 if not 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, floor and ceil are the same and we stop. If arr[mid] is less, we update floor and move low up. If arr[mid] is more, we update ceil and move high down. We repeat until low passes high. The final floor is the largest element less than or equal to target, and ceil is the smallest element greater than or equal to target. If no floor or ceil exists, we return -1 for that value.

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, others 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 of smaller elements

2. Which of the following is the correct Python syntax to find the floor of x in a sorted list arr using binary search?

easy

A. Use bisect_left and check index-1 element

B. Use bisect_right and check index-1 element

C. Use bisect_left and check index element

D. Use bisect_right and check index element

Solution

1. Step 1: Recall bisect_right usage for floor

   bisect_right(arr, x) returns insertion point to the right of existing entries equal to x.

2. Step 2: Find floor index using bisect_right

   The floor is at index bisect_right(arr, x) - 1 if index is valid.

3. Final Answer:

   Use bisect_right and check index-1 element -> Option B

4. Quick Check:

   Floor index = bisect_right - 1 [OK]

Hint: Floor index = bisect_right(arr, x) - 1 [OK]

Common Mistakes:

• Using bisect_left for floor without adjusting index
• Checking index instead of index-1
• Confusing bisect_left and bisect_right roles

3. Given a sorted array arr = [1, 2, 4, 6, 8, 10], write a function to find the floor and ceil of x = 5. What should the function return?

easy

A. [5, 6]

B. [2, 6]

C. [4, 5]

D. [4, 6]

Solution

1. Step 1: Identify floor of 5 in arr

   Floor is greatest element ≤ 5, which is 4.

2. Step 2: Identify ceil of 5 in arr

   Ceil is smallest element ≥ 5, which is 6.

3. Final Answer:

   [4, 6] -> Option D

4. Quick Check:

   Floor = 4, Ceil = 6 [OK]

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

Common Mistakes:

• Returning x if not in array
• Confusing floor and ceil values
• Choosing elements not closest to x

4. What is the output of the following code?

import bisect
arr = [1, 3, 5, 7, 9]
x = 6
floor_index = bisect.bisect_right(arr, x) - 1
ceil_index = bisect.bisect_left(arr, x)
print(arr[floor_index], arr[ceil_index])

medium

A. 5 7

B. 5 5

C. 3 7

D. 7 9

Solution

1. Step 1: Calculate floor_index using bisect_right

   bisect_right(arr, 6) returns 3 (position after 5), so floor_index = 3 - 1 = 2, arr[2] = 5.

2. Step 2: Calculate ceil_index using bisect_left

   bisect_left(arr, 6) returns 3 (position of 7), so ceil_index = 3, arr[3] = 7.

3. Final Answer:

   5 7 -> Option A

4. Quick Check:

   Floor = 5, Ceil = 7 [OK]

Hint: Floor uses bisect_right-1, Ceil uses bisect_left [OK]

Common Mistakes:

• Using bisect_left for floor index
• Mixing floor and ceil indices
• Off-by-one errors in indexing

5. The following code tries to find the floor of x in a sorted list arr. What is the error?

import bisect
arr = [2, 4, 6, 8]
x = 1
index = bisect.bisect_right(arr, x) - 1
print(arr[index])

medium

A. IndexError when x is smaller than all elements

B. SyntaxError due to bisect usage

C. Wrong floor value printed

D. No error, code works fine

Solution

1. Step 1: Calculate index for x=1

   bisect_right(arr, 1) returns 0, so index = 0 - 1 = -1.

2. Step 2: Issue with negative index

   arr[-1] accesses the last element 8 due to Python's negative indexing, but since 1 < arr[0], no element ≤1 exists, so 8 is the wrong floor value.

3. Final Answer:

   Wrong floor value printed -> Option C

4. Quick Check:

   index < 0 means no floor [OK]

Hint: Check if index < 0 before accessing floor [OK]

Common Mistakes:

• Not handling case when x < smallest element
• Assuming floor always exists
• Ignoring negative indices in Python lists