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

beginner

What happens if the floor of a number does not exist in the array?

If no element is less than or equal to the number, the floor does not exist (often represented as -1 or null).

beginner

What happens if the ceil of a number does not exist in the array?

If no element is greater than or equal to the number, the ceil does not exist (often represented as -1 or null).

In a sorted array [1, 3, 5, 7], what is the floor of 4?

A 4

B 7

C 5

D 3

3 is the greatest element less than or equal to 4.

In the same array, what is the ceil of 6?

A 5

B 7

C 6

D 3

7 is the smallest element greater than or equal to 6.

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

A The smallest element

B The largest element

C Does not exist

D The first element

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

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

A Binary search

B Insertion sort

C Bubble sort

D Linear search

Binary search reduces time complexity to O(log n) for sorted arrays.

What is the ceil of 10 in array [2, 4, 6, 8]?

A Does not exist

B 10

C 8

D 6

No element is greater than or equal to 10, so ceil does not exist.

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

Think about how to move left or right in the array to find the greatest element less than or equal to the target.

Describe the difference between floor and ceil in a sorted array with examples.

Floor is the closest smaller or equal number, ceil is the closest greater or equal number.