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

↓

mid

↓

mid

↓

mid

↓

After loop ends

↓

Floor = arr[high

↓

Ceil = arr[low

↓

Return Floor and Ceil

↓

End

We use binary search to find the target or closest elements. If found, floor and ceil are the same. Otherwise, floor is the largest smaller element, ceil is the smallest larger element.

Execution Sample

DSA Java

int floor = -1, ceil = -1;
int low = 0, high = arr.length - 1;
while (low <= high) {
  int mid = (low + high) / 2;
  if (arr[mid] == target) return new int[]{arr[mid], arr[mid]};
  else if (arr[mid] < target) low = mid + 1;
  else high = mid - 1;
}
floor = (high >= 0) ? arr[high] : -1;
ceil = (low < arr.length) ? arr[low] : -1;
return new int[]{floor, ceil};

This code finds floor and ceil of target in a sorted array using binary search.

Execution Table

Step	Operation	low	high	mid	arr[mid]	Comparison	Action	Floor	Ceil	Visual State
1	Initialize	0	6	-	-	-	-	-1	-1	[1, 3, 5, 7, 9, 11, 13]
2	Calculate mid	0	6	3	7	7 < 8?	arr[mid] < target, low=mid+1=4	-1	-1	[1, 3, 5, 7, 9, 11, 13]
3	Calculate mid	4	6	5	11	11 > 8?	arr[mid] > target, high=mid-1=4	-1	-1	[1, 3, 5, 7, 9, 11, 13]
4	Calculate mid	4	4	4	9	9 > 8?	arr[mid] > target, high=mid-1=3	-1	-1	[1, 3, 5, 7, 9, 11, 13]
5	Loop ends	4	3	-	-	-	-	7	9	[1, 3, 5, 7, 9, 11, 13]

💡 Loop ends because low (4) > high (3). Floor is arr[high]=7, Ceil is arr[low]=9.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5 (End)
low	0	4	4	4	4
high	6	6	4	3	3
mid	-	3	5	4	-
floor	-1	-1	-1	-1	7
ceil	-1	-1	-1	-1	9

Key Moments - 3 Insights

Why does the loop end when low > high?

Because the search space is empty. See execution_table step 5 where low=4 and high=3, so no more elements to check.

Why is floor taken from arr[high] and ceil from arr[low] after the loop?

Because high points to the largest element smaller than target, and low points to the smallest element larger than target after the loop ends, as shown in execution_table step 5.

What if the target is found exactly in the array?

The function returns immediately with floor and ceil equal to that element, as shown in execution_sample line with 'if (arr[mid] == target)'.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of 'high' after the action?

A 6

B 4

C 5

D 3

💡 Hint

Check the 'Action' column at step 3 where high is updated to mid-1=4.

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

A Step 4

B Step 5

C Step 3

D Step 2

💡 Hint

Look at the 'exit_note' and step 5 in execution_table where low=4 and high=3.

If the target was 7 instead of 8, what would be the floor and ceil returned?

A Floor=7, Ceil=7

B Floor=5, Ceil=9

C Floor=3, Ceil=5

D Floor=9, Ceil=11

💡 Hint

Refer to execution_sample where exact match returns floor and ceil equal to target.

Concept Snapshot

Floor and Ceil in Sorted Array:
- Use binary search with low=0, high=n-1.
- While low <= high, find mid and compare with target.
- If arr[mid] == target, floor=ceil=arr[mid].
- If arr[mid] < target, move low to mid+1.
- Else move high to mid-1.
- After loop, floor=arr[high] if high>=0 else None.
- Ceil=arr[low] if low<n else None.

Full Transcript

This concept finds the floor and ceil of a target number in a sorted array using binary search. We start with low at 0 and high at the last index. We calculate mid and compare arr[mid] with the target. If equal, floor and ceil are the same and we return immediately. If arr[mid] is less than target, we move low up to mid+1 to search the right half. If arr[mid] is greater, we move high down to mid-1 to search the left half. When low becomes greater than high, the loop ends. At this point, floor is the element at high if high is valid, and ceil is the element at low if low is valid. This method efficiently finds the closest smaller and larger elements around the target in a sorted 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 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 ≤ target, pick greatest such element [OK]

Common Mistakes:

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

2. Which of the following is the correct Java method signature to find the floor of a number in a sorted integer array?

easy

A. int findFloor(int arr[], target)

B. public int findFloor(int[] arr, int target, int size)

C. static int findFloor(int[] arr, int target) throws Exception

D. public static int findFloor(int[] arr, int target)

Solution

1. Step 1: Check Java method signature syntax

   Java methods must specify access modifier, return type, method name, and parameter types.

2. Step 2: Validate each option

   public static int findFloor(int[] arr, int target) is correct: public static int findFloor(int[] arr, int target). int findFloor(int arr[], target) misses access modifier and parameter type for target. static int findFloor(int[] arr, int target) throws Exception unnecessarily throws Exception. public int findFloor(int[] arr, int target, int size) has extra parameter 'size' not needed.

3. Final Answer:

   public static int findFloor(int[] arr, int target) -> Option D

4. Quick Check:

   Correct Java method signature = public static int findFloor(int[] arr, int target) [OK]

Hint: Java method needs access modifier, return type, parameters [OK]

Common Mistakes:

• Omitting access modifier
• Missing parameter types
• Adding unnecessary throws clause

3. Given the sorted array int[] arr = {1, 3, 5, 7, 9} and target = 6, what is the floor and ceil of 6?

medium

A. Floor = 7, Ceil = 9

B. Floor = 3, Ceil = 5

C. Floor = 5, Ceil = 7

D. Floor = 6, Ceil = 6

Solution

1. Step 1: Identify floor of 6 in array

   Floor is greatest element ≤ 6. Elements ≤ 6 are 1, 3, 5. Greatest is 5.

2. Step 2: Identify ceil of 6 in array

   Ceil is smallest element ≥ 6. Elements ≥ 6 are 7, 9. Smallest is 7.

3. Final Answer:

   Floor = 5, Ceil = 7 -> Option C

4. Quick Check:

   Floor ≤ 6 = 5, Ceil ≥ 6 = 7 [OK]

Hint: Floor ≤ target, ceil ≥ target; pick closest values [OK]

Common Mistakes:

• Choosing floor greater than target
• Choosing ceil less than target
• Assuming target must be in array

4. Consider this Java method to find floor in a sorted array:

public static int findFloor(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    int floor = -1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return arr[mid];
        else if (arr[mid] < target) {
            floor = arr[mid];
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return floor;
}

What is the bug if the array is empty?

medium

A. Returns -1 correctly as floor does not exist

B. Throws ArrayIndexOutOfBoundsException at mid calculation

C. Returns 0 incorrectly as floor

D. Infinite loop occurs

Solution

1. Step 1: Analyze behavior with empty array

   If array is empty, arr.length = 0, so high = -1. Condition low <= high is false initially, so loop never runs.

2. Step 2: Check return value when loop doesn't run

   Variable floor initialized to -1 and returned as is, indicating no floor found.

3. Final Answer:

   Returns -1 correctly as floor does not exist -> Option A

4. Quick Check:

   Empty array returns -1 floor [OK]

Hint: Check loop condition before accessing array [OK]

Common Mistakes:

• Assuming mid calculation causes error on empty array
• Expecting exception instead of -1 return
• Missing initialization of floor variable

5. You have a sorted array int[] arr = {2, 4, 6, 8, 10}. You want to find the floor and ceil for target = 1 and target = 11. What are the correct floor and ceil values for these targets?

hard

A. For 1: Floor = -1, Ceil = 2; For 11: Floor = -1, Ceil = -1

B. For 1: Floor = -1, Ceil = 2; For 11: Floor = 10, Ceil = -1

C. For 1: Floor = -1, Ceil = -1; For 11: Floor = 10, Ceil = 10

D. For 1: Floor = 2, Ceil = -1; For 11: Floor = -1, Ceil = 10

Solution

1. Step 1: Find floor and ceil for target = 1

   Floor is greatest element ≤ 1. No elements ≤ 1, so floor = -1 (not found). Ceil is smallest element ≥ 1, which is 2.

2. Step 2: Find floor and ceil for target = 11

   Floor is greatest element ≤ 11, which is 10. Ceil is smallest element ≥ 11, none exists, so ceil = -1.

3. Final Answer:

   For 1: Floor = -1, Ceil = 2; For 11: Floor = 10, Ceil = -1 -> Option B

4. Quick Check:

   Floor and ceil outside array bounds handled with -1 [OK]

Hint: Floor or ceil missing means return -1 for that value [OK]

Common Mistakes:

• Returning array ends incorrectly as floor or ceil
• Confusing floor and ceil for out-of-bound targets
• Assuming floor or ceil always exists