#binary search

[coding-quark]

MinMax Binary Search : Aggressive Cows

Question 1: Aggressive Cows Problem Statement: You are given an array 'arr' of size 'n' which denotes the position of stalls. You are also given an integer 'k' which denotes the number of aggressive cows. You are given the task of assigning stalls to 'k' cows such that the minimum distance between any two of them is the maximum possible. Find the maximum possible minimum distance

APPROACH

Since it is max of min problem we can consider binary Search

Let's first figure out what the questions is saying a) arr[i] denotes the position of the stall b) k = number of cows c) Need to maximize the minimum distance d) So according to what we've learned i need to go over the minimum values and then find maximum among them.

Figure out Minimum Distance Values: a) Now the minimum distance will be between any 2 consecutive stalls b) So we need to go over the consecutive stalls only

Figure out high and low: a) low -> 1 (minimum distance of 1 between any two stalls) b) high -> Maximum Distance between any two stalls (max - min)

Think of the f(x) function that will help us determine the feasibity of a minimum distance x a) The minimum distance, as stated can be between any 2 consecutive stalls b) if keeping this minimum distance (note: min distance means it can take more than this as well), we can fit all k cows, then it is a possible answer.

Now the modified BS part: a) if f(x) is true, then x is a possible answer. However since we're looking for MAX, we move rightward: if stalls >= k : low = mid + 1 b) if f(x) is false, all cows did not fit. That means we need to descrease the distance: else high = mid - 1

In the beginning low was possible, high was impossible. so now its inverse and our ans will be high

[frog707]

Bisection

I've encountered several otherwise-capable software developers who apparently don't know how to use bisection to locate regressions (=bugs that were introduced recently into a software project).

The basic idea is, you identify a (recent) commit A that exhibits the bug and another (older) commit B where the bug is not present. Then you pick a commit C about halfway between A and B and determine whether the bug is present there. If it is, you pick D between C and B and repeat the process. If not, you pick D between A and C.

In this way, by running a dozen or so tests, you can often identify a single commit from among thousands. It's an example of a "divide and conquer" strategy.

I spent a pleasant half hour today using bisection to locate a 3 year-old performance regression in one of my projects. Said project has 1427 commits. Back in 2022 I added code to check for OpenGL errors. For one particular workload, those changes cut the graphics frame rate by a factor of 4.

All I need now is a simple mechanism to bypass OpenGL error checking, one that won't cause me to forget that those checks are available!

[speccytechybecky]

How does the computer scientist find their breakfast?

By using a serial search

[sivaniverse]

Binary Search Algorithm

I made a new video explaining the Binary Search Algorithm. My aim is to explain Binary Search Algorithm more straightforwardly in this video. I have also tried to explain this visually with the help of an example array I took. I hope this video helps you understand about Binary Search Algorithm.

Do check it out!

[ultrachemicalgladiator]

Urgh, the photo quality is terrible, I need to figure out this studyblr stuff... Anyway, I picked a random topic to revise today, namely search algorithms for OCR A level computing. Not too difficult, just some pseudo code and maths. Essentially if your data is sorted, use binary search, if not, sort it then use binary search. (I guess linear search works in some cases). I only showed a recursive algorithm for binary search, since I prefer it. This is my first study post, please tell me what you think! Tips to improve the lighting would be much appreciated, or any other advice for that matter.

[coding-quark]

Steps to Solve Min of Max or vice versa using BS

Max of Min:

To find the minimum of the maximum in the context of a binary search, we use binary search over the possible values of the maximum. The key idea is to search for the smallest value that satisfies a feasibility condition, where the feasibility is determined by whether the maximum can be bounded by that value. Here's a structured breakdown:

Steps to Solve the Problem

Define the Search Range:

Determine the minimum possible value (low) and maximum possible value (high) for the answer. These are often based on the problem constraints (e.g., the distance between the first and last element in a range).

Binary Search Loop:

While low < high:

Compute the midpoint (mid) of the current range.

Check Feasibility: Determine if it's possible to achieve a maximum value of mid (i.e., if the condition is satisfied).

Adjust the Search Range:

If feasible, set high = mid to search for a smaller value.

If not feasible, set low = mid + 1 to search for a larger value.

Return the Answer:

Once the loop ends, low (or high) is the minimum value of the maximum that satisfies the condition.

Key Concepts

Feasibility Check: For a given candidate value (e.g., a distance, a value in an array), the check function determines whether it's possible to achieve the desired condition. This function is typically monotonic—if a value is feasible, all larger values are also feasible.

Binary Search on the Maximum: The search is over the range of possible maximum values, not directly over the array elements. This is because the problem is to minimize the maximum, not to find a specific element in the array.

Example: Placing Cows in Stalls

Problem: Place k cows in n stalls such that the maximum distance between adjacent cows is minimized.

Steps:

Search Range: low = 0, high = max(stalls) - min(stalls).

Feasibility Check: For a given distance mid, check if it's possible to place k cows such that no two are more than mid apart.

Binary Search: Use the above logic to find the smallest mid that satisfies the condition.

Another Example: Minimizing Maximum Subarray Sum

Problem: Find the minimum possible maximum of the sum of any subarray of length k in an array.

Steps:

Search Range: low = 0, high = sum of all elements.

Feasibility Check: For a given value mid, check if there exists a subarray of length k whose sum is ≤ mid.

Binary Search: Adjust the search range to find the smallest mid that satisfies the condition.

Why Binary Search Works

Monotonicity: If a value is feasible, all larger values are also feasible.

Efficiency: Reduces the search space by half in each iteration, resulting in O(log(max_value)) complexity.

Conclusion

To find the minimum of the maximum in a problem, perform binary search over the possible values of the maximum. For each candidate value, use a feasibility check to determine if it's possible to satisfy the condition. The minimum feasible value is the answer. This approach is widely used in optimization problems where the goal is to minimize the worst-case scenario (e.g., maximum distance, maximum sum, etc.).

----

Max of Min

To solve the "max of min" problem, we use binary search to find the maximum possible value of the minimum value that satisfies a given condition. This is often used in optimization scenarios where the goal is to maximize the minimum value (e.g., maximizing the minimum distance between cows, or maximizing the minimum number of coins in a subset). Below is a structured explanation of the approach, including how to detect the problem and implement the solution.

Key Concepts for "Max of Min" Problem

Binary Search on the Minimum Value:

The search is over the possible values of the minimum (e.g., distances, values, etc.).

The goal is to find the largest value that can be achieved as the minimum under the problem's constraints.

Feasibility Check:

For a given candidate value mid, the feasibility check determines whether it is possible to achieve a minimum value of at least mid.

If feasible, we can try higher values (i.e., set low = mid). If not, we need to try lower values (i.e., set high = mid - 1).

Monotonicity:

The feasibility of a value mid implies that all values less than mid are also feasible. This ensures the binary search can proceed correctly.

Example: Maximize the Minimum Distance Between Cows

Problem: Place k cows in n stalls such that the minimum distance between any two cows is as large as possible.

Steps:

Search Range:

low = 0 (minimum possible distance).

high = max(stalls) - min(stalls) (maximum possible distance).

Binary Search Loop:

While low < high:

Compute mid = (low + high) // 2.

Feasibility Check: Can we place k cows such that the minimum distance between any two cows is ≥ mid?

If feasible, set low = mid (try larger values).

If not feasible, set high = mid - 1 (try smaller values).

Result:

After the loop, low (or high) is the maximum possible minimum distance.

Feasibility Check for "Max of Min"

The feasibility check is reversed compared to the "min of max" case. For example:

In the min of max problem, we check if it is possible to achieve a maximum distance ≤ mid.

In the max of min problem, we check if it is possible to achieve a minimum distance ≥ mid.

Example Feasibility Check:def is_possible(stalls, k, min_dist): count = 1 # Number of cows placed last_pos = stalls[0] for pos in stalls[1:]: if pos - last_pos >= min_dist: count += 1 last_pos = pos if count == k: return True return count >= k

This function checks if it's possible to place k cows such that the minimum distance between adjacent cows is ≥ min_dist.

How to Detect the Problem

The problem is typically detected by the following:

Goal: Maximize the minimum value (e.g., distance, number of coins, etc.).

Constraints:

The problem involves a trade-off between values (e.g., placing cows to maximize the minimum distance).

The feasibility check is monotonic (if a value is feasible, all smaller values are also feasible).

Example: Maximize the Minimum Number of Coins in Subsets

Problem: Given an array of coins, find the maximum value of the minimum number of coins in any subset of size k.

Approach:

Search Range: low = 1, high = max(coins).

Feasibility Check: Can we select k subsets such that the minimum number of coins in any subset is ≥ mid?

Binary Search: Adjust the search range based on the feasibility check.

Key Differences Between "Min of Max" and "Max of Min"

Conclusion

To solve the "max of min" problem:

Perform binary search over the possible values of the minimum.

Use a feasibility check to determine if a given minimum can be achieved.

Adjust the search range based on the feasibility result.

The final answer is the largest feasible minimum.

This approach is widely applicable to optimization problems where the goal is to maximize the minimum under certain constraints.

[hope-and-sleep]

2025年06月18日 (禮拜三) [14/100]

I went for a walk this morning and found a rabbit :)

Anyway, there are my binary search notes. I think I can successfully write my way through a problem that requires it if I remember how to calculate mid (to avoid overflow) and low <= high, but I still don't fully understand why low <=high and not low<high... at some point, low must equal high, I guess...

Anyway, I'm going to look through a TypeScript and Node.js course today. If I finish them both quickly, then I'll do a coding test, but the rate things are going, I'll probably have to take the test tomorrow.... I hope that's not too late...

[coding-quark]

MinMax Binary Search : Maximum Book allocation

Problem Statement: Given an array ‘arr of integer numbers, ‘ar[i]’ represents the number of pages in the ‘i-th’ book. There are a ‘m’ number of students, and the task is to allocate all the books to the students. Allocate books in such a way that:

Each student gets at least one book.

Each book should be allocated to only one student.

Book allocation should be in a contiguous manner.

You have to allocate the book to ‘m’ students such that the maximum number of pages assigned to a student is minimum. If the allocation of books is not possible. return -1

Since it is a Minimum of Max problem, use binary search

Figuring out what the question is saying: a) arr[i] is the number of pages in i-th book b) m students. Each Student must be assigned a book c) ALL books must be covered (Each book must be allotted to only one student) d) c will help us figure out f(x) e) since this is min of max, we need to go over all the maximum page values, and then minimize them

We need to find the maximum possible values: a) In the worst case, each student can be assigned one book b) If one student, they're assigned all books

Figure out low and high: a) low -> Each book needs to be assigned. So low will be max(arr) so each assign is possible. b) high -> sum(arr) in case there is one student. can be assigned all books

Figure out the feasibility conditions and f(x) a) since all books need to be assigned. It should be exactly k. b) We start out by assigning one book, then add on till it becomes > MaxPages (x. as x is the maximum possible pages that can be assigned) c) we return x

BS a) == k -> we have found a possible solution. but since we want minimum move left b) we need to assign less pages so all students can be covered. move left. c) >k -> we have assigned too few pages and now books are left. so increase pages and move rightward if <= k: high = mid -1 else: low = mid + 1

Return Low (according to opposite polarity)