onenoughtone

Search Space Reduction

What is Search Space Reduction?

Search Space Reduction is a pattern that uses binary search to efficiently find an optimal value in a range, even when we don't have a sorted array to search in.

Instead of searching for a specific value, we search for the optimal value that satisfies certain conditions.

Key Concepts

Search Space: Define a range of possible answers (the search space)
Feasibility Function: Create a function that checks if a value is a feasible solution
Binary Search: Use binary search to narrow down the search space
Monotonicity: The feasibility function must be monotonic (if x is feasible, all values greater than x are also feasible, or vice versa)

Example: Square Root

Here's how to find the integer square root of a number using binary search:

Example: Minimize Maximum Distance

Here's a more complex example: minimizing the maximum distance between adjacent positions after placing m new positions.

When to Use This Pattern

Use the Search Space Reduction pattern when:

You need to find an optimal value (minimum or maximum) that satisfies certain conditions
The search space is too large for a linear search
You can define a monotonic feasibility function
The problem involves optimization with a clear objective function

Previous Next

Pattern 3: Search Space Reduction

Learn how to use binary search to efficiently find optimal values in a range.

What is Search Space Reduction?

Search Space Reduction is a pattern that uses binary search to efficiently find an optimal value in a range, even when we don't have a sorted array to search in.

Instead of searching for a specific value, we search for the optimal value that satisfies certain conditions.

Example Problem:

Problem: Find the square root of a non-negative integer x, rounded down to the nearest integer.

Search Space: [0, x]

Explanation: We use binary search to find the largest integer k such that k² ≤ x.

Key Concepts

Search Space

Define a range of possible answers (the search space) based on the problem constraints.

Feasibility Function

Create a function that checks if a value is a feasible solution to the problem.

Binary Search

Use binary search to narrow down the search space by eliminating half of the remaining values in each step.

Monotonicity

The feasibility function must be monotonic (if x is feasible, all values greater than x are also feasible, or vice versa).

Example: Square Root

Here's how to find the integer square root of a number using binary search:

mySqrt.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function mySqrt(x) {
  if (x === 0) return 0;
 
  let left = 1;
  let right = Math.floor(x / 2) + 1; // Square root can't be larger than x/2 for x > 1
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const square = mid * mid;
 
    if (square === x) {
      return mid;
    }
 
    if (square < x) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  // When we exit the loop, right is the integer square root of x
  return right;
}

How it works: We define the search space as [1, x/2 + 1] (since the square root can't be larger than x/2 for x > 1). Then, we use binary search to find the largest integer k such that k² <= x. The feasibility function checks if mid² <= x.

Example: Minimize Maximum Distance

Here's a more complex example: minimizing the maximum distance between adjacent positions after placing m new positions.

minimizeMaxDistance.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function minimizeMaxDistance(positions, m) {
  // Sort the positions
  positions.sort((a, b) => a - b);
 
  // Define the search space
  let left = 0;
  let right = positions[positions.length - 1] - positions[0];
 
  // Binary search for the minimum maximum distance
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
 
    // Check if it's possible to place m new positions
    // such that the maximum distance is at most mid
    if (canPlace(positions, m, mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
 
  return left;
}
 
function canPlace(positions, m, maxDistance) {
  let count = 0;
  let prev = positions[0];
 
  for (let i = 1; i < positions.length; i++) {
    const current = positions[i];
    const distance = current - prev;
 
    // Calculate how many new positions we need to place
    // to ensure the distance is at most maxDistance
    count += Math.floor(distance / maxDistance);
 
    prev = current;
  }
 
  // Return true if we can place at most m new positions
  return count <= m;
}

How it works: We define the search space as [0, max_distance] where max_distance is the maximum distance between any two adjacent positions. Then, we use binary search to find the smallest maximum distance such that we can place at most m new positions. The feasibility function checks if it's possible to place at most m new positions such that the maximum distance is at most mid.

When to Use This Pattern

Optimization Problems

Problems that involve finding the minimum or maximum value that satisfies certain conditions.

Examples: Finding square root, minimizing maximum values, maximizing minimum values.

Large Search Space

Problems where the search space is too large for a linear search.

Examples: Finding a value in a large range, such as [1, 10^9].

Monotonic Conditions

Problems where the feasibility function is monotonic.

Examples: If we can place k items, we can also place fewer than k items.

Decision Problems

Problems that can be transformed into a decision problem.

Examples: "Can we achieve a maximum distance of at most d?" can be used to find the minimum maximum distance.

Previous: Rotated Array Pattern Next: Boundary Binary Search

Intro Visualize Patterns Practice

onenoughtone

Back to Home

onenoughtone

Back to Home

Search Space Reduction

What is Search Space Reduction?

Search Space Reduction is a pattern that uses binary search to efficiently find an optimal value in a range, even when we don't have a sorted array to search in.

Instead of searching for a specific value, we search for the optimal value that satisfies certain conditions.

Key Concepts

Search Space: Define a range of possible answers (the search space)
Feasibility Function: Create a function that checks if a value is a feasible solution
Binary Search: Use binary search to narrow down the search space
Monotonicity: The feasibility function must be monotonic (if x is feasible, all values greater than x are also feasible, or vice versa)

Example: Square Root

Here's how to find the integer square root of a number using binary search:

Example: Minimize Maximum Distance

Here's a more complex example: minimizing the maximum distance between adjacent positions after placing m new positions.

When to Use This Pattern

Use the Search Space Reduction pattern when:

You need to find an optimal value (minimum or maximum) that satisfies certain conditions
The search space is too large for a linear search
You can define a monotonic feasibility function
The problem involves optimization with a clear objective function

Previous Next

Pattern 3: Search Space Reduction

Learn how to use binary search to efficiently find optimal values in a range.

What is Search Space Reduction?

Search Space Reduction is a pattern that uses binary search to efficiently find an optimal value in a range, even when we don't have a sorted array to search in.

Instead of searching for a specific value, we search for the optimal value that satisfies certain conditions.

Example Problem:

Problem: Find the square root of a non-negative integer x, rounded down to the nearest integer.

Search Space: [0, x]

Explanation: We use binary search to find the largest integer k such that k² ≤ x.

Key Concepts

Search Space

Define a range of possible answers (the search space) based on the problem constraints.

Feasibility Function

Create a function that checks if a value is a feasible solution to the problem.

Binary Search

Use binary search to narrow down the search space by eliminating half of the remaining values in each step.

Monotonicity

The feasibility function must be monotonic (if x is feasible, all values greater than x are also feasible, or vice versa).

Example: Square Root

Here's how to find the integer square root of a number using binary search:

mySqrt.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function mySqrt(x) {
  if (x === 0) return 0;
 
  let left = 1;
  let right = Math.floor(x / 2) + 1; // Square root can't be larger than x/2 for x > 1
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const square = mid * mid;
 
    if (square === x) {
      return mid;
    }
 
    if (square < x) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  // When we exit the loop, right is the integer square root of x
  return right;
}

Example: Minimize Maximum Distance

Here's a more complex example: minimizing the maximum distance between adjacent positions after placing m new positions.

minimizeMaxDistance.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function minimizeMaxDistance(positions, m) {
  // Sort the positions
  positions.sort((a, b) => a - b);
 
  // Define the search space
  let left = 0;
  let right = positions[positions.length - 1] - positions[0];
 
  // Binary search for the minimum maximum distance
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
 
    // Check if it's possible to place m new positions
    // such that the maximum distance is at most mid
    if (canPlace(positions, m, mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
 
  return left;
}
 
function canPlace(positions, m, maxDistance) {
  let count = 0;
  let prev = positions[0];
 
  for (let i = 1; i < positions.length; i++) {
    const current = positions[i];
    const distance = current - prev;
 
    // Calculate how many new positions we need to place
    // to ensure the distance is at most maxDistance
    count += Math.floor(distance / maxDistance);
 
    prev = current;
  }
 
  // Return true if we can place at most m new positions
  return count <= m;
}

When to Use This Pattern

Optimization Problems

Problems that involve finding the minimum or maximum value that satisfies certain conditions.

Examples: Finding square root, minimizing maximum values, maximizing minimum values.

Large Search Space

Problems where the search space is too large for a linear search.

Examples: Finding a value in a large range, such as [1, 10^9].

Monotonic Conditions

Problems where the feasibility function is monotonic.

Examples: If we can place k items, we can also place fewer than k items.

Decision Problems

Problems that can be transformed into a decision problem.

Examples: "Can we achieve a maximum distance of at most d?" can be used to find the minimum maximum distance.

Previous: Rotated Array Pattern Next: Boundary Binary Search