[oi knowledge] dichotomy, dichotomy concept, integer dichotomy, floating point dichotomy

Two points

Generally speaking, there are two points , It's natural to think of monotonous , That is, the problem can be abstracted as : F(x)
Satisfy : (1. F(x) It's monotonous namely : Increase or decrease ) ( 2. The answer for Some x value , $x\in D(f)$, D Define a domain for )

Make this impression , Mainly from : The most classic Two points problem : ( Output a number x In monotonic arrays A Subscript in ind, No output -1)
In monotonic arrays [1, 3, 5, 5, 5, 7, 9] in , Output [5] Of Far left or Far right The subscript position of , This can be handled in two

however , There are several problems :
(1, If you want to output Not the left and right ends Of 5, It is One in the middle 5 The location of , Can you give me two points ? )
(2, If you want to in Nonmonotonic array [5, 1, 10, 100, 50] In this array , look for 10 This element , Can I use two points ? )

about 1. problem , Although arrays are monotonous , But this is impossible direct Solved by dichotomy .
such as , Find out In the middle 5, It is impossible to get the answer directly in two .
( But he can get through two points to preprocess first Leftmost left and The most right Of 5 The location of , then , Take the middle position .
But this is another matter , What we're talking about here is : Direct dichotomy , You can locate the answer )

about 2 problem , Although arrays are not monotonous , But he can be divided in two . Because the left side is < 10, On the right > 10

---

therefore , The dichotomy problem , It is not simply equivalent to : monotonous

We use x Axis , As answer ans Definition domain , And ans The answer is the only , That is, at most 1 The first point is the answer
answer ans only , That's important , I'll talk about it later ; But it's not just a dichotomy , Most of the Oi problem , The answer is usually the only

.... [ans-1] [ans] [ans+1] ..... ->

First , For all x > ans, He is definitely not the answer ; be-all x < ans, He is definitely not the answer ; Only x = ans Yes, the answer .

We randomly test a point x;
If x > ans, that , be , x This point test result , We should be told : ans stay x The left side of the , For all >= x The point of , We don't have to test .
vice versa .

We make this Test functions by test( x), Its output value is : Either for left, Or right, Or equal
encounter left, Naturally Current point and Left section , Delete all
encounter right, will Current point and Right section , Delete all
encounter equal, Then we can get results .

namely : [left, left, ..., left] [equal] [right, right, ..., right], ( You can find , This and the one above x Axis , Enterprise is actually one thing )

This is the correct thinking and derivation , From the above x Axis and ans Uniqueness , Such a conclusion can be deduced .

---

And the reality , It's a little more complicated . Our test function test, It could be : right or equal; namely , It's a : Necessary condition , Not a sufficient and necessary condition
For example, monotone array : A = [7, 8, 8, 8, 9], Find the leftmost 8 The subscript position of namely ans = 2
When test( x), And x < ans when , such as test( 1), Naturally it will return left, That's for sure . because A[ x] < 8
The two are equivalent : namely (x < ans <-> A[x] < 8)
however , When test( x), And x > ans when , such as test( 5), His value 9 > 8, So the return is right Beyond all doubt .
however , about test( 4), His value is : 8, The same value as the answer , If we don't tell you 4 > ans ( Because I didn't know , ans It is unknown. , How can you know 4 and ans The relationship between … hh)
Just call test( 4), The result of finding him is : 8, Is the target value . But because there are multiple target values , Choose the leftmost .
… … Just to mention here , The target There will be repetition , but answer , That's the top x Axis It won't be repeated !! Don't mix up.
therefore , Can be determined : answer ( or = 4), ( or < 4)
namely , x > ans and A[ x] >= 8, It's not equivalent !!!
( When x > ans, Yes : A[ x] >= 8, however , ( When A[ x] >= 8 when , Is not necessarily x > ans, It could be x = ans)

namely : When test( x), If x < ans, The return value is : left; If x > ans, The return value is : right, or equal;
Here's the story , There is ambiguity , But in order to introduce the following
because , about x > ans, test It must be back right. There is no doubt that , The above definition is like this .
however , The key to the problem is : We didn't know in advance ans Value , therefore , For one x, How to know x > ans Well ?
… I have no idea ! therefore , Need to carry out Equivalent transformation

---

Equivalent transformation

From the above Binary definition (x Axis ) know , We will x Axis The answer range , Divided into 3 Parts of : (x < ans) (x = ans) (x > ans), There is also a test function test( x)

$And:test(x)=\{\begin{array}{l}left,x<ans\\ equal,x=ans\\ right,x>ans\end{array}$

And because the , We don't know ans How much is the , therefore , How to determine x < or = or > ans Well ?

introduce Calc( x) function
How to define this function , Different problems have different definitions , Therefore, there is no need to discuss
But there are two things that must be met :
… 1, Its domain And above x Axis ( That is, the answer definition field ), It's exactly the same
… 2, The return value , There must be . ( Of course , The type and meaning of its return value , It also varies according to the question )

introduce Bool( y) function
All from Calc( x) The output value , You have to get in Bool( y) function
The Bool function , Must satisfy :
… 1, The return value must be bool value
… 2, For all Bool( Calc( > ans)), The values are the same , For example, remember as A;
… For all Bool( Calc( < ans)), The values are the same , For example, remember as B;
… Must have : A != B, Namely or A = true, B = false;, or A = false; B = true

$$At\; this\; time\; there\; is:\{\begin{array}{l}Bool(Calc(x))=A,x<ans\\ Bool(Calc(x))=B,x=ans\\ Bool(Calc(x))=C,x>ans\end{array}$$

And there are : A != C

because , B Or equal to A, Or equal to C;
here , It can be divided into two situations : [A, A, C] and [A, C, C]
Simpler expression : [true, true, false] and [false, true, true] Two kinds of ( about [false, false, true] The situation of , After unified negation

that , He is in line with the face Two points The definition of : [left, equal, right] Do you ?

Conform or not , The key is to see : For one x( That is, the point on the answer field ), Can you judge , He And ans answer , Of Left right relationship
namely : Is in ans The left side of the , Or on the right .

For any one x( The value of the answer field ), After the same function ( It's the one above Bool( Calc( x)) function ), You'll get one or true, or false, and , [ans] The values on the left and right sides are different
such as , [true, true, false], When you get true, Conduct l = mid; Otherwise to : r = mid - 1;
Again , [false, true, true], When you get true, Conduct r = mid; Otherwise to : l = mid + 1;

therefore , We deal with it like this , Is to meet the two points

---

summary

---

summary

The dichotomy problem needs to meet :

1, answer ans Is the only one.

2, Answer field , be called : Binary domain

3, All values of the binary definition field , After the same function , Get one Boolean value

4, all < ans Boolean value != all >ans Boolean value , ans The Boolean value of is T or F All possible .

5, With < ans and ans and > ans, this 3 From the Boolean value of the interval ,
It must eventually form : [T, T, F] or [F, F, T] or [T, F, F] or [F, T, T]
namely : ( The Boolean values on the left and right sides are different , And Point of division It must be in the middle ans Location )
We call this form : Boolean duality

---

Algorithm

1, Establish a binary domain D Meaning and scope of .
( such as , It's an array subscript [0, n-1], It's still an integer , Or real numbers

2, Definition Calc( x) function , And its definition field is equal to D, And must have a return value .
Definition Bool( y) function , The return value is bool type

3, according to Calc( x) stay [< ans], [ans], [> ans] Three intervals , Write the corresponding three Yongzhen style

$$\begin{gathered} such\; as,The\; most\; common\; situation\; may\; be:\{\begin{array}{l}Calc(x)>K,x<ansItype\\ Calc(x)>=K,x=ansIItype\\ Calc(x)<K,x>ansIIItype\end{array} \\ KIs\; the\; constant\; in\; the\; meaning\; of\; the\; title \end{gathered}$$

this 3 Formulas , Need to meet :

a, I, II, III Three formulas , All are Yongzhen style
… such as , For all Calc( > ans) Its value , It has to be > K Of
… It can't be said that there is one Calc( > ans) yes <= K Of .

b, take II type , and I type or III type Conduct Compound operation ( That is to say : Logic or operation )
( Which formula to merge with , Need to try )
To become 2 Forever true , Write it down as : IV type and V type
such as II And I Merge to form : $\{\begin{array}{l}>=K,x\le ans,IVtype\\ <K,x>ans,Vtype\end{array}$
such as II And III Merge to form : $\{\begin{array}{l}>K,x<ans,IVtype\\ \in R,x\ge ans,Vtype\end{array}$
And IV type And V type It must be contradictory . ( namely IV type Logic and V type As the result of the : Permanent falsehood )
… therefore , II And III The merger of , It's illegal. . because IV yes V Sufficient conditions of , One $>K$ Number of numbers , It must be $\in R$ Of
therefore , II And I The merger of , It's legal. . namely , For any number ( That is to say Calc( x) Value ), Its satisfaction IV type , Must not be satisfied V type

Last , selection II type The compound ( It's the one above IV type ), It is defined as : Bourgeon , Then the other compound formula is : Boolean fake
If II type ( That is the answer. ), Is in IV type , be l = mid;, otherwise : r = mid;

… In fact, what we do , It's just one. Equivalent transformation , This is also the essence of dichotomy
… That is, the initial idea is : For values on a binary domain x, We need to know : x and answer ans The relative left and right positions of
… however , answer ans Of course we don't know ! therefore , Cannot directly judge x And ans Relative position of
… therefore , For one x, Let it pass through a y = Calc( x) Function to get a y value , And this y The value is monotonic ;
… let me put it another way , y value Can be converted to true/false, And in the binary domain Of answer ans Endpoint About , There are different Boolean values .

---

l, r;
while( l < r){
    
	mid;
	if( Bool( Calc( mid)) == true/false){
    
		l = mid;  or  r = mid;
	}
}

---

give an example

---

stay A = [ 10, 1, 20, 30, 30, 30, 50, 40] in , find Far left Of 30 The subscript ans

1, The definition field of dichotomy is : The array subscript

2, Definition Calc( x) by : int Calc( int _x){ return A[ _x]; }, Its domain of definition is Answer field

3, Definition Bool( y) by : Definition here , According to Calc( x) To analyze ; This y value , That is to say Calc( x) value
… Calc( x) < 30, When x < ans
… Calc( x) = 30, When x = ans
… Calc( x) >= 30, When x > ans
… Definition bool Bool( y){ return y >= 30;}, You will get : [false, true, true], accord with Boolean duality
… ( This involves Mathematical logic Knowledge , the 3 individual
… If , We define it as return y <= 30;, here , about x > ans when , It will be true, It will be false, This is not true. Boolean duality ** The definition of
… If defined as : return y < 30, obtain : [true, false, false], therefore , This definition is also ok
… therefore , [true, false, false] and [false, true, true], In dichotomy , It's interchangeable , It is equivalent. .
… … Difference is that : The former is if( false){ r = mid;}, The latter is if( true}{ r = mid;}; But are r = mid;
… But if it is defined as : return y > 30, here , about x > ans, It will be true, It will be false, Can not be .
… Okay , Definition Bool by : return y >= 30;, obtain : [false, true, true]

4, Bisection algorithm : if( true == Bool( Calc( mid))){ r = mid;} else{ l = mid + 1;}

---

OI Answer key LeetCode 2040. The second of two ordered arrays K Small product

Topic link

---

Title Description
Let's simplify it here , An array A, Please export A[ ind] Value
1, A The array is unknown
2, A[ < ind] <= A[ ind] and A[ > ind] >= A[ ind]
3, A[] The value is +- 1e18
4, Array from [1] Start

---

1, The definition field of dichotomy is : A[] Value , namely [-1e18, 1e18] Integer field of

2, Definition Calc( x) by : A Array , < x Number of elements of .
This specific definition is arbitrary , If this definition is wrong , Just change
Calc( x) </=/> ind , When x > ans when
… such as : [1, {2}, 3], here Calc( 3) = ind (A[ ind] = A[ 2] = {2})
… such as : [1, {2}, 2], here Calc( 2) < ind
… such as : [1, {2}, 2, 3], here Calc( 3) > ind
Does not meet the requirements of Boolean two segment

2, Definition Calc( x) by : A Array , <= x Number of elements of
Calc( x) </=/> ind , When x < ans when
… such as : [1, {2}], here Calc( 1) < ind
… such as : [2, {2}], here Calc( 2) = ind
… such as : [2, {2}, 2], here Calc( 2) > ind
Does not meet the requirements of Boolean two segment

---

…, How to define Calc All wrong , Just explain This is not a dichotomy !

however … Your above analysis is wrong !!!
Calc( x), His domain of definition is : Binary domain , and 1 The binary domain of definition is : range , No Subscript !!

therefore , If the array is : [2, {2}, 2], ans = A[ ind] = 2
When x > ans when , How could there be : Calc( 2) Well ? It must be : Calc( > 2), Will belong to x > ans The situation of
Empathy , When x < ans when , How could there be : Calc( 2) Well ? It must only be : Calc( < 2)

therefore , The question of dichotomy , Not simple ! It's very rigorous !

Walk again :
2, Definition Calc( x) by : A Array , < x Number of elements of .
Calc( x) < ind , When x < ans when , I type
Calc( x) < ind , When x = ans when , II type
Calc( x) >= ind , When x > ans when , III type
What we got before is : Calc( x) </=/> ind , When x > ans when , This is a wrong analysis
such as , When [1, {2}, 2], Calc( x) = Calc( > ans) = Calc( > 2, such as 2.5) = {1, 2, 2} > ind = 2
such as , When [1, {2}, 3], Calc( x) = Calc( > ans) = Calc( > 2, such as 2.5) = {1, 2} = ind = 2
however , non-existent Cacl( x) < ind The situation of !! because : Calc( 2.0001) No comparison ind Not yet

therefore , II type It can be summarized in I type , so , Conform to Boolean two segment

2, Definition Calc( x) by : A Array , <= x Number of elements of .
Calc( x) < ind , When x < ans when , I type
Calc( x) >= ind , When x = ans when , II type
Calc( x) >= ind , When x > ans when , III type
What we got before is : Calc( x) </=/> ind , When x < ans when , This is a wrong analysis
because < ans Number of elements of , It must be < ind Of . from The first ind The element begins , Will >= ans

Back to the point

2, Definition Calc( x) by : A Array , < x Number of elements of .
Calc( x) < ind , When x < ans when , I type
Calc( x) < ind , When x = ans when , II type
Calc( x) >= ind , When x > ans when , III type

II And I Can be combined
< ind, When x <= ans
>= ind, When x > ans

so if( Calc( mid) < ind){ l = mid;}

Integer dichotomy

• Satisfy : D(f) Is an integer field ( Can contain negative numbers )

---

In terms of dichotomy ,

while( l < r){
    mid = ( l + r) / 2;
}

there /, It can be Round up , It can also be Round down

---

according to ( Increase or decrease ), It is divided into : r = mid or l = mid, Two dichotomy
Either way , The smallest bisection interval is : The length is 2 The range of ; Plus while( l < r) Conditions

You know , When l == r - 1 when :

• about r = mid The situation of , mid Not for r. Otherwise, there will be a dead cycle
  because : mid = (l + r) / 2 = r, If it is Round up , Then the equation holds
  so , This situation , Must be Round down
• about l = mid The situation of , mid Not for l. Otherwise, there will be a dead cycle
  because : mid = (l + r) / 2 = l, If it is Round down , Then the equation holds
  so , This situation , Must be Round up

division

Binary algorithm , It's just mid = (l + r) / 2 when , Using the division
We said above , there division Under different dichotomy needs , It is divided into : On , Next integer , Two kinds of

namely , Naturally, there are two kinds : mid = (l + r) / 2, mid = (l + r + 1) / 2
That's right , Premise is : there /, It means : Round down

however , stay C++ Next , devide / yes : towards 0 integer , namely x / 2: When x>0 Time is the next divisible ; Otherwise, divide it up

therefore , You wrote : mid = (l + r) / 2, mid = (l + r + 1) / 2
When it comes to : Negative field when , It's a mistake !!! ( for example : -1 / 2 = 0, It means that this is rounding up )

---

terms of settlement :

• Custom division , Must be unified as Round down

• Use x >> 1 The way , Shift operation ( That is, complement ) He is Round down Of !

Floating point binary

• Satisfy : D(f) Is a real number field

Because there is no rounding problem for floating-point numbers , therefore , Unlike integer bisection algorithm, it is more delicate , Its template is still very simple :

constexpr double Eps_ = 1e-8;

double l, r;

while( r - l > Eps_){
    
	double mid = (l + r) / 2;
	
	if( Check( mid)){
     l = mid;}
	else{
     r = mid;}
}

assert( l <= r);
assert( fabs(l - r) <= Eps_); 
//  Of course, these two sentences don't need to be written ,  Just to tell you ,  There must be this result 

the reason being that Floating point numbers , It must involve precision problem , This is also a very important issue .

---

The basic accuracy will be higher : 1e-8 about . Because two points are exponential growth
Even if your scope is Integers 1e6, precision 1e-8, Is the total 1e14 = 2^40, It's just 40 No more than

---

Unlike integer bisection ( Finally, there must be : l == r), The last half of a floating-point number , There must be : l < r, This is very important !!!

Although in eps Under precision , Can be regarded as l == r, but , This is not eps The role of !!!,
eps The role of , Just control to find the answer precision , let me put it another way , Just to control the number of two points .

from double From the perspective of , There must be : l <= r.
and , And the most important point : l <= ans <= r,
Of course , In terms of probability , Basic it is : l < ans < r, because , Floating point numbers can accurately represent , Only in a few cases
therefore , We will basically follow l < ans < r The situation of .

such as , The answer of two points is : ans = 3.1415, that , The final answer , It must be : l = ans - delta, r = ans + delta, among delta > Eps_
namely , such as : l = 3.14149999, r = 3.14150001. It's important , Almost two points , It must be like this

that , At this time, the answer required by the question , Basically 3 In this case : In the reserved x On the premise of decimal places , Conduct ( rounding ) or ( Round down ) or ( Round up )
about ( Round up and down ) problem , The general problem is : Will result in *= 10000 after , Conduct On / Round down , Output an integer

• rounding : If the first [x + 1] position yes >= 5 Of , be [x] position += 1; This is familiar
• Round down : take [x+1, x+2, ...] All bits are discarded , Before retention only x position
  such as , 3.1415abcde become 3.1415
• Round up : If [x+1, x+2, ...] position Not all for 0, Is the first [x] position += 1
  such as , 3.141500001 -> 3.1416; 3.14150000 -> 3.1415

---

Take the example above , Retain 4 Decimal place , That is, you must finally get 3.1415

The following is the focus of floating point binary

If it is ( rounding )
Use l or r, It's all right !
Will get 3.1415

If it is ( Round up )
Only use l!!
because , r = 3.141500001, and 0.00001 Rounding up is 1
such as , r *= 10000 After is : 31415.00001, The rounding up of this number is 31416, And what we want is : 31415

If it is ( Round down )
Only use r!!
because , l = 3.141499999, Rounding below will get : 3.1414
such as , l *= 10000 After is : 31414.99999, The lower rounding of this number is 31414, And what we want is : 31415

---

Example

• https://www.acwing.com/problem/content/description/104/

---