Floor and Ceil in Sorted Array in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

The floor of a number is the greatest element in the array that is less than or equal to that number.

beginner

What is the ceil of a number in a sorted array?

The ceil of a number is the smallest element in the array that is greater than or equal to that number.

intermediate

Why is binary search useful for finding floor and ceil in a sorted array?

Binary search helps find floor and ceil efficiently by repeatedly dividing the search space in half, reducing time from linear to logarithmic.

intermediate

If the target number is smaller than all elements in the array, what is the floor and ceil?

Floor does not exist (no element ≤ target), ceil is the smallest element in the array.

intermediate

If the target number is larger than all elements in the array, what is the floor and ceil?

Floor is the largest element in the array, ceil does not exist (no element ≥ target).

What does the floor of a number represent in a sorted array?

A The smallest element greater than or equal to the number

B The average of all elements less than the number

C The greatest element less than or equal to the number

D The first element in the array

Floor is the greatest element less than or equal to the target number.

What is the time complexity of finding floor or ceil using binary search in a sorted array?

A O(n)

B O(n log n)

C O(1)

D O(log n)

Binary search divides the search space in half each step, resulting in O(log n) time.

If the target number is exactly equal to an element in the array, what are floor and ceil?

A Floor is smaller element, ceil is larger element

B Both floor and ceil are that element

C Floor and ceil do not exist

D Floor is the first element, ceil is the last element

When target equals an element, floor and ceil are that element itself.

If the target is smaller than all elements, what is the floor?

A No floor exists

B Largest element in array

C Target itself

D Smallest element in array

No element is less than or equal to target, so floor does not exist.

Which method is best to find floor and ceil in a sorted array?

A Binary search

B Linear search

C Sorting the array first

D Random guessing

Binary search efficiently finds floor and ceil in O(log n) time.

Explain how to find the floor and ceil of a number in a sorted array using binary search.

Think about how to move left or right in the array to find closest smaller or larger elements.

Describe what happens when the target number is outside the range of the sorted array elements for floor and ceil.

Consider the smallest and largest elements in the array.

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