Floor and Ceil in Sorted Array in DSA Javascript - Build from Scratch

Floor and Ceil in Sorted Array

📖 Scenario: You are working on a search feature for an online bookstore. When a user searches for a price, you want to find the closest book prices available in the store that are just below or equal to the searched price (floor), and just above or equal to the searched price (ceil).

🎯 Goal: Build a program that finds the floor and ceil values for a given target price in a sorted array of book prices.

📋 What You'll Learn

Create a sorted array of book prices

Create a target price variable

Write logic to find floor and ceil values for the target price

Print the floor and ceil values

💡 Why This Matters

🌍 Real World

Finding floor and ceil values is useful in pricing, searching, and recommendation systems where you want to find closest matches to a target value.

💼 Career

Understanding floor and ceil concepts helps in roles like software development, data analysis, and algorithm design where efficient searching and data handling are required.

1

Create a sorted array of book prices

Create a sorted array called bookPrices with these exact values: [10, 20, 30, 40, 50, 60, 70]

DSA Javascript

// Create the sorted array bookPrices with the given values
// Your code here

Hint

Use const to create the array and include all values in ascending order.

2

Create a target price variable

Create a variable called targetPrice and set it to 35

DSA Javascript

const bookPrices = [10, 20, 30, 40, 50, 60, 70];
// Create the targetPrice variable with value 35
// Your code here

Hint

Use const to create the variable and assign the value 35.

3

Find floor and ceil values for the target price

Write a function called findFloorAndCeil that takes arr and target as parameters and returns an object with floor and ceil properties. Use a for loop with variable i to iterate over arr. Inside the loop, update floor to the largest value less than or equal to target, and ceil to the smallest value greater than or equal to target. Initialize floor to null and ceil to null before the loop.

DSA Javascript

const bookPrices = [10, 20, 30, 40, 50, 60, 70];
const targetPrice = 35;

// Write the findFloorAndCeil function below
// Your code here

Hint

Use a loop to check each value. Update floor if the value is less than or equal to target. Update ceil if the value is greater than or equal to target and less than current ceil.

4

Print the floor and ceil values

Call the findFloorAndCeil function with bookPrices and targetPrice, store the result in result, then print Floor: followed by result.floor and Ceil: followed by result.ceil using two separate console.log statements.

DSA Javascript

const bookPrices = [10, 20, 30, 40, 50, 60, 70];
const targetPrice = 35;

function findFloorAndCeil(arr, target) {
    let floor = null;
    let ceil = null;
    for (let i = 0; i = target && (ceil === null || arr[i] < ceil)) {
            ceil = arr[i];
        }
    }
    return { floor, ceil };
}

// Call the function and print the floor and ceil values
// Your code here

Hint

Store the returned object in a variable and use console.log to print floor and ceil values on separate lines.

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