Floor and Ceil in Sorted Array in DSA C - 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 greatest element less than or equal to the number

B The average of all elements less than the number

C The smallest element greater 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 of size n?

A O(log n)

B O(n)

C O(n log n)

D O(1)

Binary search divides the search space in half each step, so it runs 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 the first element, ceil is the last element

B Floor and ceil are both that element

C Floor and ceil do not exist

D Floor is smaller element, ceil is larger element

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

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

A The smallest element

B The largest element

C No floor exists

D The middle element

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

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

A Sorting the array first

B Linear search from end

C Linear search from start

D Binary search

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 binary search narrows down the search space and updates floor or ceil candidates.

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

Consider the array boundaries and what floor and ceil mean.

Practice

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

easy

A. The smallest element strictly less than the number

B. The smallest element greater than or equal to the number

C. The average of all elements less than the number

D. The greatest element less than or equal to 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 ceil or incorrect concepts.

3. Final Answer:

   The greatest element less than or equal to the number -> Option D

4. Quick Check:

   Floor = greatest ≤ number [OK]

Hint: Floor is always ≤ number, pick greatest such element [OK]

Common Mistakes:

• Confusing floor with ceil
• Thinking floor is strictly less than number
• Mixing floor with average or median

2. Which of the following is the correct C syntax to find the middle index in binary search for array of size n?

easy

A. int mid = (0 + n) / 2;

B. int mid = 0 + n - 1 / 2;

C. int mid = (0 + (n - 1)) >> 1;

D. int mid = n / 2;

Solution

1. Step 1: Understand middle index calculation in binary search

   For array indices 0 to n-1, middle is (0 + n-1) / 2 or equivalent.

2. Step 2: Analyze options for correct syntax and efficiency

   int mid = (0 + (n - 1)) >> 1; uses bitwise right shift for division by 2, which is efficient and correct for integer mid calculation.

3. Final Answer:

   int mid = (0 + (n - 1)) >> 1; -> Option C

4. Quick Check:

   Mid = (start + end) >> 1 [OK]

Hint: Use (start + end) >> 1 for efficient mid calculation [OK]

Common Mistakes:

• Using n instead of n-1 as end index
• Forgetting parentheses causing wrong precedence
• Using floating division instead of integer

3. Given the sorted array arr = {1, 3, 5, 7, 9}, what is the floor of 6?

medium

A. 7

B. 5

C. 6

D. -1

Solution

1. Step 1: Identify elements less than or equal to 6

   Elements ≤ 6 are 1, 3, 5.

2. Step 2: Find greatest among these

   The greatest element ≤ 6 is 5.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Floor(6) = 5 [OK]

Hint: Floor is largest ≤ target in sorted array [OK]

Common Mistakes:

• Choosing 7 which is greater than 6
• Assuming floor equals the number if not present
• Returning -1 incorrectly when floor exists

4. Consider this code snippet to find ceil in a sorted array int ceil = -1; for(int i=0; i= x) { ceil = arr[i]; break; } }. What is the main issue?

medium

A. It may return wrong value if array is not sorted

B. It does not handle empty array

C. It returns first element ≥ x, which is correct for ceil

D. It finds floor instead of ceil

Solution

1. Step 1: Understand the code logic

   The code returns the first element in array ≥ x, which is correct if array is sorted.

2. Step 2: Identify assumptions and issues

   If array is not sorted, first element ≥ x may not be the smallest such element, so ceil is incorrect.

3. Final Answer:

   It may return wrong value if array is not sorted -> Option A

4. Quick Check:

   Ceil requires sorted array for correctness [OK]

Hint: Ceil logic needs sorted array to work correctly [OK]

Common Mistakes:

• Ignoring array sorting requirement
• Confusing ceil with floor
• Not checking for empty array before loop

5. You have a sorted array arr = {2, 4, 6, 8, 10}. If you want to find the ceil of 11 using binary search, what should be the returned value?

hard

A. -1

B. 11

C. 10

D. Error

Solution

1. Step 1: Understand ceil definition and array elements

   Ceil is smallest element ≥ target. Here, target is 11, which is greater than all elements.

2. Step 2: Check if any element ≥ 11 exists

   No element in array ≥ 11, so ceil does not exist, return -1.

3. Final Answer:

   -1 -> Option A

4. Quick Check:

   No element ≥ 11 means ceil = -1 [OK]

Hint: If target > max element, ceil is -1 (not found) [OK]

Common Mistakes:

• Returning last element as ceil incorrectly
• Returning target itself if not found
• Not handling no ceil case properly