Бинарный поиск (Анна Антонова) 19 ноября

Hello everyone!

Oh my God, what an echo!

Скажите, а как сейчас со звуком?

Норм?

Все отлично.

Это успех.

Ну что, тогда погнали к лекции.

Сейчас я пошарю презентацию.

Только это могу переделать.

So, guys, hello again.

Tell me, please, can you see the board now, is everything okay?

Everything is fine.

Sorry for the delay.

I tried to figure out all sorts of technical matters.

Well, let's go to the lecture.

We have a bin search with you today, as you may have already seen in the plan.

Tell me, please, are you familiar with this concept at all?

Or plus or minus?

It seems to be familiar.

Yeah.

Yeah, great.

Look, the lecture plan for today is the following.

We will briefly go over the main idea of bin search, like what it is in general.

Let's see what built-in functions we have, remember the bin search in response and try it to find the roots of the equation.

This is probably the most useful thing that can be for you at the Olympiad, at the municipality itself.

So, well.

Let's go!

Let's start with the search for a value in the array.

What is the traditional task when we want to write a bin search?

We are given an assorted array.

Traditionally, we believe that the array is sorted by age, and we want to find any element for the logarithm in it.

Tell me what a logarithm is.

Let's do it.

The function of Yaroslav is strong.

Well, look, yes, the answer is correct, that the logarithm is the function of the reverse increase in the degree.

It is not very clear what it is, but the main thing is to understand what it gives us in general.

Look, the function of the increase in the degree grows very, very quickly.

Well, that is, 2 to the hundredth is something incredibly big in general.

Therefore, the logarithm, on the contrary, grows very slowly.

So slowly that the logarithm from n to 10 to 9 is no more than 30.

This means that we have n log n, with n to 10 to 6, generally calmly goes.

When you try to estimate the asymptotic, you can roughly assume that the logarithm of n is 30, or if you have... One second, if... What is it?

Now.

Or if n is 10 to the sixth, then you can think that the logarithm of n is about 20.

If you ever need a more accurate estimate, you know.

But usually you can just think that it's 30.

Good.

Remembered what a logarithm is, now we need to solve our problem.

What are we doing in general?

Let's come up with some kind of array, the simplest one, like 1, 2, 3, 4, 5.

And we want to find the number 3 in it.

Let's see what we're going to do.

I need some kind of answer from you guys, come on.

With a close look, we will notice that there are three of them.

This is strong.

This is strong.

Uh-huh, uh-huh, uh-huh.

Full overkill for N.

Well, if nothing else comes to mind at all, then yes, at the Olympics you need to write a full overbill for N. This will give you at least some amount of points.

Not full, of course, but... Divide the array in half.

Yes, thank you, thank you.

Let's go.

What is the main idea?

We need to remember.

We divide... Oh my God.

Divide the array in half.

Here we do not clearly divide in half, because we have an odd number of elements.

Therefore, okay, let's divide approximately in half.

Here, on the one hand, we will have two, on the other three.

Or vice versa, the difference does not really matter to us.

Let's look at the element that is here in the middle.

We are lucky that it is three.

Found.

Good.

But if we were looking for a number, for example, four.

then we would have to think further.

Okay, we found the number 3.

What do we know about the number 4 and 3?

We have 4 more than 3, which means that the entire left part of the mass is obviously no more than 3.

It's clear why, right?

Well, because our mass is growing, so if its last element is the largest,

then all the other elements in the array are even smaller.

Therefore, we can simply throw out the left part of the array with a calm soul.

And then solve the problem for the remaining piece, for this part.

Here.

But it is assumed that, as you boldly answered me in the chat, you know all this perfectly.

Therefore, we will not delay and go to the implementation, as we write it with you.

Can you see the code now?

Yes?

Yes, great.

Let's run through what is happening here, what we are doing.

Well, I don't think there should be any questions here.

We just enter the data, enter our array, enter our x.

Next, what are we doing?

We set the left and right boundaries of the search bin.

This is the piece of the array that we are looking at now.

And it is worth noting that, first of all, we have L and R,

set not as 0 and n-1, which would be quite logical, because we have the first element of the mass is zero, the last is n-1.

But it is convenient to think that the element of delta is the one that is obviously less than x.

What could be the problem here?

What if we don't have the number x in the mass at all?

Okay, let's go.

Alexander, is it scary if there is no x in the mass?

Well, look, look, then we may have a situation that you have one of the borders of L and R,

as it were, will go beyond the boundaries of the mass itself, that's why we initially set them to Daniel in Python, no, we write on the pluses, look, let's run it, let's see how it works, here we had our example there 5

elements we are looking for the number 3 found well and if we tried to look here for a number like 7 it is too big why is this happening well look at us we can just clearly display our

We see that we have R.

This is exactly the index that points to the answer.

It points to the fifth position.

I remind you that the indexation goes from zero, and therefore the fifth position is here, beyond the boundary of the mass.

If we put r equal to 4, that is, n minus 1, then...

we would not have this situation that we flew out of the massif, because we were led by too large a number, it would not have arisen, we would have stuck here on the fifth element, we would have revealed it.

Let's just touch it with our hands, as if it had happened.

Here, look.

We set the number r as n-1, that is, we made it to the right border of the array, as it were, to the last real existing element.

And what do we see?

That the code found us a wonderful answer of 5, said that here it is, your number 7, 5.

You know, like in that meme, where 6, 4.

Similarly, why do we have l minus 1?

Well, on the contrary, we may have a situation that we want to find some small value.

Oh, what?

Oh, how!

What happened now?

Just a second.

Here it is!

Light magic happened.

Everything is fine, sorry.

Look, what happened here.

We entered a very small number, which is smaller than all the numbers in the array.

And when we iterated with the bin search, we ended up ... Mikhail, last time the bin search was also counted for the number 7.

Yes, I just copy-pasted the input data, I inserted it, then deleted the last number 7, but for some reason he decided to ignore this deletion and counted the answer for him.

In general, it is similar.

We see that we rely on our left, originally set border, when our number, which we are looking for, is too small.

Therefore, in order not to worry, not to enter any additional checks, it is possible to always write the left and right border so that we have enough of them.

Sometimes it is considered that there is a minus infinity on the minus of the first position, and on the nth position, that is, here, behind the five, there is a plus infinity.

But that's the way it is.

Maybe it will be easier for someone to think this way.

This is the traditional implementation of the mass search bin.

Once again, it is important to remember that we have l minus 1, r is n.

What do we do inside the file itself?

Well, we find the middle, compare it with the desired number, move the boundaries depending on this.

If you suddenly, for some unknown reason, this is generally very rare, you will be given a mass that is sorted by growth, not by decline, then it will be enough to change here.

R and L in places?

Well, almost, almost.

What's the matter?

The fact is that it indicates to us, in fact, the search is not looking for a specific number,

to the border of our search engine.

Here it is worth drawing.

What?

Chat, I see something wrong.

Intermittent?

Sad, apparently the university Internet is not very good.

Okay, it's already normal.

Good.

Look, how useful it is to think about bin search in general.

That here we have our array.

There are some numbers here.

And all these numbers are divided into two multiples.

Here, all the numbers are less than or equal to x.

And here, all are strictly larger.

And in fact,

What we do is look for this border in the search engine.

It is quite important to understand that we are not looking for a number in the bin search, almost never, but the border between two multiples.

And how do we find it?

It is difficult for us to express the border with an index, because it passes between two elements of the mass, so we clamp it between our two indicators L and R.

at the end of the search process, we have L and R are next to each other and the border is clamped between them.

This is such a cool abstraction to imagine that you

there is your border LR, and initially this line that you are looking for, it is somewhere between them, wherever, and you slowly move your borders, and you have less and less space left for the oscillation of your finite border.

But in fact, this bin search that I showed is quite rarely written, because if you suddenly want to find the bin search value in the array, you do it with a built-in function.

Now we will move on to it.

What built-in functions do we have in C++?

what they are doing, what they are looking for.

By the way, maybe you are familiar with this?

Tell me.

Yes.

Well, I see that some are positive, some are negative.

Well, something new has come up, great.

Look, in fact, we have two useful functions.

lower bound and upper bound.

What do they do?

Let's show it on the code.

Look.

If in the first code we just took and found our boundaries L and R, and these were indexes, then the built-in function works a little differently.

It returns such an entity as an iterator.

And in general, now, in order to write a municip, it is absolutely not necessary to understand what it is.

It is enough to remember that in order to convert an iterator

index, it is enough to subtract the pointer to the beginning of your vector from it, here is the pointer to the beginning of the vector, this is a begin, but everyone remembers it so chat something here some memes went likes dislikes and so what

Mikhail, if you put an asterisk, this is also a good question, by the way, that if you have an iterator, you can rename it by putting an asterisk in front of its name, what will happen, it will seem to turn

immediately to the value, but usually it is not very useful, and knowing the index is much more useful for you, because by index you know the index, it's incredible, right?

And you can get the value.

After renaming, you will only get the value, so if you are not very good at iterators, now you just need to remember that you run the lower bound or upper bound function,

and you read from it the indicator for the beginning.

So you will just get the index of your entry.

What is the difference between lower bound and upper bound now?

Let me show it on an example.

Let's say we have 6.

And we are looking for the number 3 again.

Look, lower bound returns us an iterator here.

It finds the number 3 itself.

upper bound suddenly returns 4 to us.

What does this mean?

This means that our upper bound is looking for not less, not more or equal, but strictly more.

That is, if you have a value block here, where the three are, where our x-axis is, then the upper bound will return the pointer to the next one behind this block

element.

You can draw it beautifully.

Look, here you have your array.

It is divided into three parts.

Here the number is less than x, here it is equal to x, and here it is greater than x.

Then what?

Then your lower bound returns the pointer here.

Upper bound, here.

Are there any questions about what happened now?

Python's son.

Hello.

More or equal and less or equal.

No, look.

If you want...

No, look, you have one more or equal, and the second is strictly more.

By default, there are no simple built-in functions in order to look for something less or equal.

Well, yes, if you want to find the first element that is strictly smaller, then you run lower bound and make a minus one from it.

That lower bound minus one is strictly smaller.

Mikhail, so what is confusing you now?

Yes, you ...

Okay, another question in the chat.

What if we suddenly found out that this block X is not there?

That is, in fact, it is empty.

Then, in this case, both lower bound and upper bound will point to the same element, to the first element strictly greater than x.

And another point is that if you have all the numbers less, that is, you have...

and this block is also suddenly not, then you have both lower bound and upper bound will point to the element behind the mass, that is, to a point and but this is not so important because you are here with this subtraction, then you just get n and you can just like with an ordinary index, you need to check whether your found

the index is in the array, and if it is in it, then you can turn to it and output the answer.

Just look, in fact, it is really rare to have a task where you need to find an element equal to x.

But yes, Philip in the chat correctly writes that if you need to do exactly this, that is, check the presence of X, you can tie such a thing as Philip wrote.

In general, if you have such a task in front of you, then you can do some kind of set.

So, hypothetically.

So, how?

Are we going further?

So, they ask me to turn off the web to save the Internet.

Maybe it makes sense, by the way.

Well, why not?

Okay, well, let's move on.

Next, we have a search by answer plan.

In general, it can be used in a very large class of tasks, but there are so many of them that it is better for us to focus on one classic simple one.

This task is known as the cow in the barn.

What does it consist of?

We have marked n points on the line, not necessarily with equal distance, that is, we are given their coordinates.

We want to paint k points, exactly k, and we want these points to be as far away from each other as possible, that is, so that the minimum distance between the two of them is maximum.

How to solve this at all?

Do you know this?

Tell me.

Uh-huh, uh-huh.

Andriipin search.

This is you, of course.

And how did you guess?

Interesting.

Uh-huh.

Well, look, you can carefully look at the presentation and see the inscription BIN search by answer.

Try to understand, according to the theory of the ChatGPT, I condemn, I condemn, but there will be no such thing in the municipality, and there is no such thing at the Olympics at all.

So, we look at the slide, we see the name BIN search by answer.

What does it mean?

It means that we will choose an answer.

Okay, how can we do this?

Well, look, it is obvious that if we set between points some distance, conditional plus infinity, and we want all points to be at a distance of at least plus infinity, well, we will not succeed.

Yes, that is, this is our right border.

The right border is plus infinity.

That is, we will definitely not displace.

At the same time, what distance can we require so that we can definitely put a point?

1.

Yes, in general, 1 is also suitable, but you can make it even harder and say that yes, 0.

We put L0.

That is, well, there will be 0 between any two points for sure.

Okay, then what is our answer to the task?

What can we exactly say about it?

Well, that it lies somewhere between L and R, right?

Yes, well, yes, it's logical, it's logical.

Here.

Moreover, we have some values.

Until some point, here we can consistently take, increase L, and until some point everything will be okay, okay, we will have such a number of points at such a distance, and then hop, and that's it, and we won't be able to at some point.

That is, there ...

For zero, OK. For one, OK. What is the random number?

101, OK. And for 102, we broke down.

And then, if we could not fit them at a distance of 102, then at a greater distance we will definitely not be able to.

And so on to R. That is, we have all our possible answers divided into two groups, into two halves.

Can we fit it at some point at such a distance, and then we can't?

So, chat, how are you doing?

tolerable so I see some troubles with understanding the conditions tell me if it is necessary to repeat it again or it seems to have figured it out already like what does it mean to repeat or not to repeat so good I see an ambiguous reaction means it is necessary to repeat see

some example, for example, that here we have a point, a point, a point, then a long distance, there is still some group of points.

We want to paint two points so that they are as far as possible.

As far as possible?

It's like in our case.

It's like this.

Yes?

Yes.

Good.

And if we wanted to put three points?

Well, we could, for example, try to do it like this, right?

But this is not an optimal option, because, look, we can take our third point and move it a little to the right.

Then it will be here at a distance of two and here at a distance of, well, how much?

A lot.

That is, we want to distribute our points in a straight line so that they are all as far away from each other as possible.

And formally defining the concept of how far away from each other is possible, we say that we maximize the minimum distance between the two points.

That is, we take, look at our painted points, find the distance between each of them.

находим среди всех этих расстояний минимальные на нашей картинке это где это вот тут вот тут наше минимальное расстояние мы хотим его максимизировать ok стало стало лучше ребят да да да окей все

Mikhail, how can we understand if we can place the dots?

This is the right question, and we will now move on to this.

But let's first get back to this moment here.

Is it clear to everyone that we

We insert points at some distance, increase this distance, and then at some point, once and that's it, and now it doesn't fit.

And for each distance greater than the critical one, we won't fit either.

That is, everything is divided into two halves, all our numbers, that so much fits, but no more fits.

Can you solve this problem with a formula?

No, you can't.

Not at all.

Well, at least because your points are not at the same distance from each other, but they are in some exact coordinates.

If they were all 1, 2, 3, 4 and so on, then, of course, no.

Come on, I need to hear, to see the understanding in your eyes.

Is it true that it is clear that before some value it comes in, and after it everything does not come in?

Okay, rather yes.

Okay, then we have the last point.

How can we understand that we can place these points at such a distance?

In fact, this is not very difficult, we will just be greedy to arrange them.

Greed, greed, does everyone know what greed is?

It seems that you will have it at the end.

In short, yes, greed is a mortal sin.

Look, the main idea of ​​greed, it is sometimes called stupidity in a different way, that we can just take it, take it, we can't, go on.

For example, here we have our dots.

One, two, three.

And we want to place the dots at a distance of at least two.

Can't you see?

Everything is visible, okay?

Funny, I thought that only I have this panel.

I did not know.

Okay.

Okay, how are we going to place the dots?

We will go from left to right.

That is, now we are standing here.

Well, our dot is not painted, and, in general, nothing prevents us from painting it.

Hop, painted.

Good.

Let's move on.

Now we stand here.

Does something prevent us from painting this point?

Well, yes, this point prevents us, because they are adjacent, the distance between them is 1, and we want a distance of at least 2.

Therefore, we cannot paint this point, we miss it and go to the next one.

We come here.

Can we already paint this point?

Well, yes, we have a distance to the previous painted point, here, it is 2.

This is just our required distance.

Okay, we can paint, paint.

Go further.

Go further, go to this point.

Well, there is no coordinate axis, but, in short, I meant...

that here is the distance 2.

Ouch, I can't see.

Distance 2.

And here is 3.

Okay, can we paint this point?

Well, yes, again, the distance to the previous painted one we have 2.

Nothing prevents us from painting.

Let's go to the next one.

We can't paint this one, it's too close to the already painted one.

And we go to the last one, it's far enough.

Here is a distance of, like, how many?

Four.

This is enough, we paint it.

Thus, we just go through and greedily set these points.

Is there an intuitive understanding that such an algorithm will give us the maximum number of points that are generally possible?

Good.

Excellent.

Prove that the distance is exactly 2, not more.

Look, Roman, we ...

Let's check if it is true that the distance 2 enters.

That is, look, we do not know how to find the answer, but we know how to check whether the answer suits us.

That is, what did we do?

We set the points as much as we can.

And then we look, is it true that our number of painted dots is at least k?

That is, is it true that we have painted a sufficient number of points?

If yes, then what?

This means that our number belongs to this half.

If not, then to this one.

Dmitry, and then?

Then there will be a light magic of bin search.

But now you need to realize this thought, that if

that we can check whether our answer can fit us at all.

That is, is it true that by setting such a fixed distance between points, we can paint a sufficient number of points?

And how do we use it next?

And then?

We look at another word in the heading bin search.

There is also a union between them.

And what are we going to do?

We will look for our answer in the bin search.

That is, what are we doing?

How do we generally conduct an ordinary bin search?

That we put our ...

I'll take some other color.

Blue.

We put our left border.

put our right border yes and something there we move we take m so we take we poke m m we got 102

What can we do?

We can take and run this greedy algorithm for our m and calculate what is the maximum number of points at such a distance.

And, let's say, it turns out that we do not have enough points.

What does it mean?

It means that m points, oh, m points, sorry, the distance m is too much.

So we can take and move the border r here.

Yes?

Let's remember what r is.

We have r. This is the distance at which we will definitely not be able to paint.

Roman, look, infinity is usually not infinity in fact, but just some big number, like 10 to the ninth, conditionally.

Well, because to get to infinity is really the same task.

Andrey, 10 to the 20th is a lot, because you just won't get into Int, and even in Long-Long.

Yes, Philip, right.

This is a number that is definitely greater than the answer.

And L is definitely less or equal.

Yaroslavin128, it's very, well, it seems to be written like that, yes, I don't remember for sure, but it's not very pleasant to work with him, at least because it doesn't come out normally into the console.

In general, it is not necessary to use IN-128T, if only you are not sure of this one thousand percent.

For my entire Olympic life, it was of no use to me.

Okay, let's go, let's go look at the code of all this, what is happening with us.

This is a code in general, not specifically for our task, but just for all tasks of this kind.

What's going on with it?

Let's figure it out.

First of all, you see, we put our LR.

as I said, quite large and quite small.

Sometimes, if you don't want to think at all, don't think at all about what your minimum limit is, you can take it and write here minus infinity.

Look, this is info.

It's just that you have somewhere there at the beginning of the code there is const

int, inf equal to many, like 2e9, for example.

A better style would be to write 1e9.

Like this.

Yaroslav, yes, Constanta and Pravda, according to the code style, it is customary to write in caps, but we are preparing for the Olympics, and there the code style is not so important.

But if you want to write beautifully, then yes, it is better to write in caps.

Look, the son of a python, in order to say something like that, first of all, you need to think.

This is useful in general, but not always, because there is a risk that you will think wrong.

And specifically here it seems that you really thought wrong, because you have a number of points,

is not related to the distance between them.

Well, that is, if you have to put two points there, and you have some 1000 and 2000 coordinates, for example.

Okay, got it, super.

Next, look what happens.

This code, in general, here,

almost the same as in the bin search for the array.

The only thing that differs from us is the check function.

What is a check?

What is this function?

Check from m returns true if

M, roughly speaking, goes in.

Well, yes, in our case, this is a check, is it true that we have a minimum distance?

In the opposite case, what?

Then we can just move L.

Otherwise, we move R, and in the same way as in the bin search for the array, we move and find the border.

We output L. Why L, not R?

Well, because according to the definition of our borders, L is what goes in, R is what does not go in.

Put the distance between one and the last point in the inf.

Almost.

You need the distance between one and the last point plus one.

Because between one and the last point can get in if you paint the first point and the last one.

Again, we can instead of plus inf.

write max distance plus one.

You can max...

distance plus 1.

It is important not to forget this plus 1.

But, again, you have to think about it.

Why is it plus 1?

Let's go back to the previous slide.

You see, your r is

at what distance we will definitely not paint, that is, what is definitely more, so if you put the maximum distance, it may turn out that we will take to paint the first and last point, we need to paint two points and everything is fine, and we think that this value is inevitably more, everything will break

But if you are not sure, in some more complex tasks, it happens that you are not sure what you should put as the right and left borders.

And then you can just put minus inf and plus inf.

It won't take long at all.

Let me remind you that with inf 10 to 9, this thing will work for 30 iterations, 31.

Very little, in general.

Okay, let's see the code.

So, so, what?

Where is this from?

Look, here I did not write the check function in the obvious form.

Instead, I implemented the Max Points function.

What does it do?

It goes through the array with our coordinates and just puts the maximum number of points it can.

But we already discussed this with you, that we just greedily go from left to right.

Okay, what's going on?

We create, first of all, an auxiliary variable last.

This is the coordinate of the last painted point.

Initially, you can put it as minus infinity.

By the way, yes, it's strange that I have it written like this instead of writing minus infinity.

That's better.

Roman, are you greedy?

it is not always ineffective in our task, on the contrary, it is as effective as possible because well, we just can't put more points than we put such an algorithm usually shorter again what is the idea of ​​a greedy algorithm in general you will have a lesson about it later but in short, let's say that

I don't know, there is some kind of task about money there.

You do something there, you get money.

And what is a greedy algorithm?

It's when you just want, you can get money, you go, you get money, don't think about it, just take everything you can take.

If this is a positive value, it is clear that if you can go to the flea market, they will take your money there, you don't need to do that.

And if you can go and sell something, you take it, go and sell it and maximize your profit.

And in some models, in some tasks, this is really okay.

Well, let's say you have a limited set of actions that you can go to work, some normal one.

If you have a more complex model, then a greedy algorithm is not always optimal.

For example, you have the opportunity to go to work and go to study.

With a greedy algorithm, you will immediately go to work to maximize your profit right now.

With some other algorithm, not greedy, you can think like this, yeah, but if I go to study, I will start earning more after I graduate, right?

And that's why you don't go to work right away, but you go to study first.

So, when you go to study first, it's not a greedy algorithm.

Well, if you die of hunger, it's sad, of course, but don't do that.

Maybe there will be a scholarship there.

So, that's all, it's not so important.

So, the point is that if you are thinking about, maybe I should go to study, or maybe I should not paint this point right now, but postpone it for later, then this is not a greedy algorithm.

And if you are sure that you can do it, then this is a greedy algorithm.

And here we have just a greedy algorithm.

Why?

Because we take, we check, we can paint a dot, and if we can, then we immediately paint.

That's it, and we don't do anything else.

Returning to the task, yes.

How do we check if we can paint a point?

Well, we look at the distance between it and the last painted one, we compare it with the required distance.

If we have already moved enough away from the painted point, then we paint it.

What do we have?

We update the last value.

I remind you that this is the coordinate of the last painted point.

And also, we are not just doing it for fun, we calculate how many points we can paint.

Therefore, we increase our counter and in the end return the number of painted points.

Python's son, I understand correctly that you are confused by why this greed works, that is, why this really returns the maximum number of points.

Well, look, the global idea is that you just, well,

If you can paint a dot now, then you have absolutely no reason to paint it later.

How can I say it?

Hmm.

Well, look, if you try for some reason to paint the point not now, but to paint, for example, the next one after it, then this life will not do you any better, because you will just have the possibility

on the piece that is on the right, which you have not yet passed, less opportunities to put a point.

At the same time, when you put a point now, you do not worsen your situation in any way.

Here.

Today we will not prove this strictly.

In general, if there is no intuition, you can draw a little by yourself.

Here.

Well, in general, proving greedy is such a pleasure.

Okay.

I think we figured out the MaxPoints function.

We can now move on to the part of the code that picks up the answer.

We see the code on the search bar.

The main difference between what is inserted into the presentation and what we have here in the broadcast is not a check, but a check that the maximum number of points is suitable for us.

So, Philip, if we can paint a dot, then we ...

This and the previous painted one.

If you mean the previous painted one, then yes.

That's it, okay, okay.

So.

That's it, let's go back to our bike.

What's going on with us?

We find the maximum number of points that can be set at a distance of at least m. If it is less than k, then our m is too big.

If it is too big, we move the right border.

Otherwise, we move the left border.

In general, it seems to be all.

Are there any more questions on this task, or can we move on to the final part of the lecture?

Everything is super.

Great, great, wonderful.

Okay, then the last mini-theme is the search for the roots of the equation.

Sometimes I used this thing, something like in the region, in the first task.

Traditionally, this task is for the formula.

But I could not normally come up with this formula.

I had some kind of equation that had to be solved, I did not know how.

And in general, if you know that your equation ...

Okay, this is all a lyrical digression, we will not be very distracted.

In general, look.

If you have some kind of function, usually it's something like a multiple of f from x with some odd degrees.

Well, why odd?

Because they definitely always grow, but there can be more complex functions.

The main thing is to be sure that your function f monotonously grows.

Then we can find the root of the equation f from x equal to some number by bin search.

Usually zero, but a more universal case is c. How will it look like at all?

Here we have our function chart.

By the way, did you go through all the functions at all?

No, well, almost all of them, yes, some of them are not.

In general, I hope you have an understanding.

We have x, we have y.

And our function looks like this.

In general, we do not know how, we only know that it does not go down.

I drew badly, it looks like it's going down.

Now again, hands, hooks.

Something like this.

Okay.

And we want to find out where it turns to zero.

Well, here we see in the picture, yes, that here.

But in general, this is not very clear.

You can try to come up with something formulaic.

Again, it will not always work out.

But it will always work out what to do.

You can fix two points, for example, this one and this one.

The left one, in which our function is smaller, lower than the point we are looking for.

And the right one, which is definitely larger.

That is, these will be our L and R. Next, what are we going to do?

We will turn to the middle.

And look, is this middle higher than zero or lower?

If higher, then what are we doing?

Tell me.

Tell me what we do in the case when f is greater than zero.

Well, yes, c, but let's simply consider that ...

So.

Uh-huh, uh-huh.

The opinions have slightly diverged, but the main answer is yes, that we can throw this part out of consideration.

Because there the function only grows, there is too much.

Okay, and then we continue to do the same thing, already here we will divide in half, move again, there again we will divide in half.

The problem is that

Unlike the previous tasks, our function is a continuous thing.

Well, that is, how can we understand that we can stop in the bin search?

That is, when did we stop before?

When we rested there in two adjacent elements.

Well, for example, there we had L.

3R4.

That's all.

And how to understand here that it's time for us to stop?

Because we have infinitely many numbers between any two numbers.

That is, we can infinitely repeat our operation, divide in half and go down to one and a half.

Yes, Alexey, that's right.

You can even less.

Usually they write a hundred.

Well, what is the classic solution?

Look, we are still asked the answer, well, with some error.

Well, that is, for example, if the error there is some ten thousandth conditionally, then probably no one will even notice that you did not find the real answer, right?

Therefore,

You can either create an epsilon variable, like... Epsilon is a very small number, and we check whether it is true that between L and R there is more than epsilon, but this is difficult.

And what do they usually do?

They just perform an iteration of the search bin some fixed number of times.

like 100 and stop.

It's easier to understand by looking at the code.

Here, look.

That is, we just start an iteration counter, an iteration of our algorithm, and with each iteration we increase it, reach 100 and finish.

Why?

Why do we have enough of this for high accuracy?

Well, look, we have 2 to the hundredth.

This is something incredibly big.

Well, that is, our function 2 to some extent grows terribly quickly, and with the same speed our accuracy grows.

Let's run it, let's check if it's true.

Look, the function f looks like something at all, something disgusting, something scary.

I don't want to look for the roots of such a thing on my own.

Let's find where it turns to zero.

So that you do not think that I am deceiving you, I literally call f from this found value, I put it out.

Yes, here it is cubic.

The parabola, which is square, it has a problem.

It is not monotonous.

That is, about the function x cubed, there, this is it.

Can we say that it is monotonous?

Yes, it is symmetrical and we can only consider the piece on which it grows, but if, for example, they tell you there x squared plus 10, then you need to think about something.

Yes, you can.

Are you right that if we have a function

not monotonous, then we can break it into pieces on which it is monotonous and run bin search in each.

You can do that.

Look, another very important thing that you need to remember, write down somewhere.

This is a conclusion with accuracy to some signs.

Let's say

You are asked in the task to display the answer with accuracy up to, I don't know, well, usually they ask for 6 or 9 characters.

And by default, the pluses do not cope with this.

That is, here they displayed 6 characters and stopped.

And if they ask for 9 characters in the task, then we import this library here.

I will not, perhaps, read this word.

I do not know how it is normally read.

It has such things as fixed and set-precision.

They must be used together.

What is set-precision?

It is a thing that says, bring me exactly so many numbers.

And fixed says, bring

this is after the point so many numbers, that is, if you write just fix it and just sit down, then what a minute

These are some cool ones.

Yes, here, here, I found an example, look.

Without fixed, it displays 6 characters, including those that were before the point.

That is, there are only 6 characters here, and we want exactly 6 characters after the comma.

Therefore, we must write fixes.

If there are any questions left, it's time to ask them.

bin search for the root of the number, well, look, in general, we can also write, like, here we can write, let this thing return x squared, and the only thing that needs to be done is to search from zero, after all,

Because if we look at all the numbers, then it will not be monotonous.

And from what root?

From 49 I know the root.

Everything worked out great.

So, the son of a python.

Can we use two search engines?

In general, no, depending on what you mean by any equation.

If we could solve any equation for n log n, the mathematicians would kiss our hands, but unfortunately...

It's hard to see which argument in setPrecision.

6.

In setPrecision, we write the number of characters after the comma that we want to display.

What is your Ubuntu distribution?

If you forgot, you can display it through toString.

Philip, I don't know.

I always write like this.

I don't know what toString does.

function from the beginning of the lesson.

Stepan, what exactly do you mean?

What exactly is the function?

I can show you, but in general, you can see it later in the presentation, we will throw it away.

Gleb, yes, plus inf is 10 to the ninth.

What is C?

C is just a number.

some number that we are usually given.

Look, this is a short form of recording, like 2 and 9 zeros.

In what university do I study?

I study at the best university, at CU.

In general, everyone, go, I advise everyone.

Yes, Stepan, I'll show you now, I understand what you mean.

Here they are, lower bound and upper bound.

You can look at them.

Mikhail, what do you mean?

In the sense of when the lesson will appear, I don't really understand.

In the contest, contests, contests.

Today, quite soon, in general, after the lesson, it will be posted.

Let's see, there are still questions about the search engine.

Aizat, yes.

In general, almost everyone can go to the university, it seems to me.

Yes, in general, everyone.

So, well, I see that the questions on the subject of the lecture are over.

Yes, the questions on the subject of the lecture are over.

Oh no, we can solve adequately according to the schedule.

Well, in general, yes.

Yes, if desired, you can do such a thing.

Binary classification in degree?

Oh, that's sudden.

But you definitely won't need it in the municipality.

If you need to multiply a lot, maybe you open a python and do it there.

For today, yes, for today we are done.

In general, I think that if you have no more questions, you can leave.

Yes, guys, thank you all for listening, for sitting in your free time.

Good luck to everyone.

And it's good to decide the contest.

Especially good luck to us and Nisa, this is the main thing.

See you all, bye-bye.