Binary search and binary answer

Split template

Because bisection is not just a simple search for a number . It can be used to find the position of the dividing point between satisfying and unsatisfying properties . So when you remember the template , We have to explain it in terms of properties .

Two steps ：
1. Divisional nature
2. describe check Code statements where the properties are met
3. Determine if +1

for instance ： Now let's give an ordered list of numbers , inquiry n Time , Return the initial position and end position of the number respectively

1 1 1 2 3 3 3 3 5 7 9

Such as digital 3 The starting position of is 4 and 7（ Subscript from 0 Start ）
You have to split it in two , We have to find the corresponding properties .

notes ：
1. There must be a dichotomy in the division of properties , That is, the dividing point is an empty set , Without elements .
2.check Function is always describing the condition that the object conforms to the property

The starting position ：

When it comes to finding the starting position ：>=x Is satisfying in nature ,<x Is not satisfied with the nature of . therefore check The function is a[mid]>=x

End position ：

Finally, consider whether +1 problem .

 Left contraction （r = mid） No addition 1,  Shrink right （l = mid） Add 1

The code is as follows ：

int find1(int x)// Minimum subscript 
{
    
    int l = 0, r = n - 1;
    while(l < r)
    {
    
        int mid = l + r >> 1;
        if(a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    if(a[l] == x) return l;
    else return -1;
}

int find2(int x)// Maximum subscript 
{
    
    int l = 0, r = n - 1;
    while(l < r)
    {
    
        int mid = l + r + 1 >> 1;
        if(a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    if(a[l] == x) return l;
    else return -1;
}

A-B Number pair

A-B Number pair
There are two ways to solve this problem , One is hash enumeration , One is to enumerate first and then divide .

---

Hash idea ： Initialize the array with hash , Get the number of times each number appears . because C It is known that . therefore A-B = C You can enumerate A, obtain B.B = A - C, Then we can get the result by hashing B The number of occurrences in the array , Join in ans Then you can .

Time complexity analysis ： The hash is initialized to O(N), enumeration A The time complexity is O(N), Query hash time complexity is O(1), So the total time complexity is O(N)

---

Dichotomous thinking ： Let's enumerate A, And then we get the corresponding B Value , Use bisection to find out whether the array exists B So the value of the , And count how many times （ So you have to sort the array first ）, Join in ans that will do .

Time complexity analysis ： Sort O(NlogN）+ enumeration O(N) + Two points O(logN). So the total time complexity is O(NlogN)

Two points ac Code ：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 200010;

int n, c;
int a[N];
long long res;

int find1(int x)
{
    
	int l = 0, r = n - 1;
	while(l < r)
	{
    
		int mid = l + r >> 1;
		if(a[mid] >= x) r = mid;
		else l = mid + 1;
	}
	if(a[l] == x) return l;
	else return -1;
}

int find2(int x)
{
    
	int l = 0, r = n - 1;
	while(l < r)
	{
    
		int mid = l + r  + 1 >> 1;
		if(a[mid] <= x) l = mid;
		else r = mid - 1;
	}
	if(a[l] == x) return l;
	else return -1;
}

int main()
{
    
	cin >> n >> c;
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	sort(a, a+n);
	for(int i = 0; i < n; i++)
	{
    
		int x = a[i];
		int l = find1(x - c), r = find2(x - c);
		if(l != -1 && r != -1) res += (r - l + 1);
	}
	cout << res;
}

Cut down trees

Cut down trees
Examination site ： Two points .
notes ： The title requires that the cut wood be as long as possible , So our saws should be as short as possible .
So the nature of the division is

On the left <= x Is to meet the saw as short as possible , On the right side, the saw is not as short as possible .
check Function depends on whether the saw is as short as possible . The saws should be as short as possible because the wood is larger than the equal minimum

---

ac Code

#include <iostream>

using namespace std;

const int N = 1e6 + 10;

int n, m;
int a[N];
int ans;

bool check(int x)
{
    
	long long sum = 0;
	for(int i = 0; i < n; i++) sum += (a[i] - x > 0 ? a[i] - x : 0);
	if(sum >= m) return true;
	else return false;
}

int find()
{
    
	int l = 0, r = 1e9;
	while(l < r)
	{
    
		int mid = l + r + 1 >> 1;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
	return l;
}

int main()
{
    
	cin >> n >> m;
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	ans = find();
	cout << ans;
}

The attacking cow

The attacking cow
The difficulty of dichotomy is not the nature of division , The difficulty lies in check Function writing . That is, how to verify the correctness of properties . This problem is experienced .

Examination site : Two points
1. The question is about the closest distance , It implies that it can be solved by dichotomy .
2. The greatest nearest distance is to find x The maximum of . So the properties can be divided into <=x and >x
3.x Is the nearest distance ,x The smaller it is , The more cattle the shed can hold ,x The bigger it is , The shed may not hold all the cattle .
4. So we can judge by the number of cows in the shed x Whether it can meet the maximum nearest distance , And can put down all the properties of cattle
5. Start herding cattle from the leftmost shed , Every greater than or equal to x The distance between the cows , The maximum number of cows that can be put down （ Greedy thoughts ）, This is it. check The idea of function

ac Code ：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100010;
int a[N];

int n, m;

bool check(int x)
{
    
	int k = 1, last = 1;
	
	for(int i = 1; i < n; i++)
		if(a[i] - last >= x)
		{
    
			k++;
			last = a[i];	
		}
	
	return k >= m;
}

int find()
{
    
	int l = a[0], r = a[n - 1];
	while(l < r)
	{
    
		int mid = l + r + 1 >> 1;
		if(check(mid)) l = mid;
		else r = mid - 1;
	}
	return l;
}

int main()
{
    
	cin >> n >> m;
	for(int i = 0; i < n; i++) scanf("%d", &a[i]);
	sort(a, a + n);
	int ans = find();
	cout << ans;
}

Floating point binary template

bool check(double x) {/* ... */} //  Check x Whether it satisfies certain properties 

double bsearch_3(double l, double r)
{
    const double eps = 1e-6;   // eps  Representation precision , It depends on the accuracy of the topic .
    while (r - l > eps)// Or you could write it as for(int i = 0;i < 100;i++) This is equivalent to two points 100 Time ,N/2 Of 100 Power 
    {
        double mid = (l + r) / 2;
        if (check(mid)) r = mid;
        else l = mid;
    }
    return l;
}

notes ： because double No rounding down , Therefore, there is no need to consider whether +1 了 .

Cubic equation of one variable

Cubic equation of one variable
Examination site ： Floating point binary
1. The cubic equation has three solutions , If there is only one interval divided by two , Only one value can be obtained .
2. skill ： Divide the whole section into [i, i+1) Such a small area （ The title says that the difference between each root is at least 1, So it's like this ）. Split each cell
3. The reason why the interval is divided into left opening and right closing is to prevent repeated solutions
4. How to determine that an interval has roots ？ Existence theorem of zero point
5. How to dichotomy ？ Draw a few examples to find the rules ：

f(l) * f(mid) > 0, be l = mid

f(r) * f(mid) > 0, be r = mid 

notes ： Bisection can only find the root inside the interval , Cannot find the root of the endpoint . So we have to judge whether the endpoint is the root .

ac Code ：

#include <iostream>
#include <cmath>

using namespace std;

double esp = 1e-4;
double a, b, c, d;

double f(double x)
{
    
	return a * x * x * x + b * x * x + c * x + d;
}

int main()
{
    
	cin >> a >> b >> c >> d;
	for(int i = -100; i <= 100; i++)
	{
    
		double l = i, r = i + 1;
		if(abs(f(l)) <= esp) printf("%.2lf ", l);
		else if(abs(f(r)) <= esp) continue;
		else if(f(l) * f(r) < 0)
		{
    
			while(r - l > esp)
			{
    
				double mid = (l + r) / 2;
				if(f(mid) * f(l) > 0) l = mid;
				else r = mid;
			}
			printf("%.2lf ", l);
		}
	}
}