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

Concept Flow - Floor and Ceil in Sorted Array

Start with sorted array and target

↓

Initialize low=0, high=array.length-1

↓

While low <= high

↓

Calculate mid = Math.floor((low+high)/2)

↓

Compare array[mid

↓

low=mid+1

↓

Loop until low > high

↓

Return floor and ceil based on final low and high

We use binary search to find floor and ceil by narrowing search space until low passes high.

Execution Sample

DSA Javascript

function floorAndCeil(arr, target) {
  let low = 0, high = arr.length - 1;
  let floor = -1, ceil = -1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (arr[mid] === target) return { floor: arr[mid], ceil: arr[mid] };
    else if (arr[mid] < target) {
      floor = arr[mid];
      low = mid + 1;
    } else {
      ceil = arr[mid];
      high = mid - 1;
    }
  }
  return { floor, ceil };
}

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

Execution Table

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

💡 Loop ends because low (4) > high (3), floor is 6, ceil is 8

Variable Tracker

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

Key Moments - 3 Insights

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

Because arr[mid] is less than target and could be the closest smaller value. See step 2 and 3 where floor updates to 6.

Why does the loop stop when low > high?

Because the search space is empty, meaning we have found the closest floor and ceil. See step 8 where low=4 and high=3.

What if target equals arr[mid]?

We return floor and ceil as that exact value immediately. This is shown in the code line inside the loop checking arr[mid] === target.

Visual Quiz - 3 Questions

Look at the execution table, what is the value of floor after step 4?

A 6

B 10

C -1

D 8

💡 Hint

Check the 'floor' column in row for step 4 in execution_table.

At which step does the condition low > high become true?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

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

If target was 10, what would be the floor and ceil returned?

A floor=8, ceil=10

B floor=10, ceil=10

C floor=10, ceil=12

D floor=6, ceil=8

💡 Hint

Recall the code returns exact match floor and ceil immediately if arr[mid] === target.

Concept Snapshot

Floor and Ceil in Sorted Array:
- Use binary search with low=0, high=length-1
- Calculate mid = Math.floor((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 until low > high
- Return floor and ceil 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, we return that value as both floor and ceil. If arr[mid] is less than target, we update floor and move low up. If arr[mid] is greater, we update ceil and move high down. We repeat until low passes high, then return the last floor and ceil values found. The execution table shows step-by-step how low, high, mid, floor, and ceil change. Key moments clarify why floor updates when arr[mid] < target, why the loop stops when low > high, and what happens on exact match. The visual quiz tests understanding of these steps and outcomes.

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 or equal to the number

C. The average of all elements less than the number

D. The smallest element strictly 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 with options

   The greatest element less than or equal to the number matches this definition exactly, while others describe ceil or incorrect 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
• Thinking floor must be strictly less than number
• Mixing floor with average or median

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

easy

A. Use Math.floor(x) directly on array

B. Use a for loop from 0 to arr.length and return first element greater than x

C. Use arr.indexOf(x) to find floor

D. Use a while loop with start = 0, end = arr.length - 1, update mid and check arr[mid] <= x

Solution

1. Step 1: Understand binary search for floor

   Binary search uses start and end pointers, calculates mid, and checks if arr[mid] <= x to move start or end accordingly.

2. Step 2: Evaluate options

   Use a while loop with start = 0, end = arr.length - 1, update mid and check arr[mid] <= x correctly describes binary search logic for floor. Options A, B, and C are incorrect or irrelevant.

3. Final Answer:

   Use a while loop with start=0, end=arr.length-1, update mid and check arr[mid] ≤ x -> Option D

4. Quick Check:

   Binary search with arr[mid] ≤ x finds floor [OK]

Hint: Binary search with arr[mid] ≤ x finds floor efficiently [OK]

Common Mistakes:

• Using linear search instead of binary search
• Using indexOf which only finds exact matches
• Misusing Math.floor which works on numbers, not arrays

3. What is the output of the following JavaScript code?

const arr = [1, 3, 5, 7, 9];
function findFloor(arr, x) {
  let start = 0, end = arr.length - 1, floor = -1;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] <= x) {
      floor = arr[mid];
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return floor;
}
console.log(findFloor(arr, 6));

medium

A. 6

B. 5

C. 7

D. -1

Solution

1. Step 1: Trace binary search for floor of 6

   Initial start=0, end=4, floor=-1. mid=2 (arr[2]=5) ≤ 6, floor=5, start=3. mid=3 (arr[3]=7) > 6, end=2. Loop ends.

2. Step 2: Return floor value

   Floor found is 5, which is the greatest element ≤ 6.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Floor of 6 in [1,3,5,7,9] is 5 [OK]

Hint: Floor is last arr[mid] ≤ x during binary search [OK]

Common Mistakes:

• Returning mid index instead of value
• Confusing floor with ceil
• Not updating floor variable correctly

4. Identify the bug in this JavaScript function to find the ceil of a number x in a sorted array arr:

function findCeil(arr, x) {
  let start = 0, end = arr.length - 1, ceil = -1;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] >= x) {
      ceil = arr[mid];
      end = mid + 1;
    } else {
      start = mid + 1;
    }
  }
  return ceil;
}

medium

A. The line end = mid + 1; should be end = mid - 1;

B. The line start = mid + 1; should be start = mid - 1;

C. The initial value of ceil should be 0 instead of -1

D. The while loop condition should be start < end instead of start <= end

Solution

1. Step 1: Analyze binary search update for ceil

   When arr[mid] ≥ x, we update ceil and must move end to mid - 1 to search left side for smaller ceil.

2. Step 2: Identify incorrect update

   The code incorrectly sets end = mid + 1, which moves end right, causing infinite loop or wrong result.

3. Final Answer:

   The line end = mid + 1; should be end = mid - 1; -> Option A

4. Quick Check:

   For ceil, move end left with end = mid - 1 [OK]

Hint: For ceil, move end left; for floor, move start right [OK]

Common Mistakes:

• Moving end pointer in wrong direction
• Confusing ceil logic with floor
• Incorrect initial ceil value

5. Given a sorted array arr = [2, 4, 6, 8, 10], write a function to find both floor and ceil of a number x. What will be the floor and ceil of x = 5?

hard

A. Floor = 5, Ceil = 5

B. Floor = 6, Ceil = 4

C. Floor = 4, Ceil = 6

D. Floor = 2, Ceil = 10

Solution

1. Step 1: Understand floor and ceil definitions

   Floor is greatest element ≤ x, ceil is smallest element ≥ x.

2. Step 2: Find floor and ceil for x=5 in arr

   Elements ≤ 5 are 2 and 4; greatest is 4 (floor). Elements ≥ 5 are 6, 8, 10; smallest is 6 (ceil).

3. Final Answer:

   Floor = 4, Ceil = 6 -> Option C

4. Quick Check:

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

Hint: Floor ≤ x max, Ceil ≥ x min in sorted array [OK]

Common Mistakes:

• Swapping floor and ceil values
• Assuming floor or ceil equals x if not present
• Choosing wrong boundary elements