Hello there!

Today is Persian New Year's day, Nowruz!

I wish this year be an amazing year for you!

I hope to see all you in RED...

Before contest

Codeforces Round 940 (Div. 2) and CodeCraft-23

2 days

Register now »

Codeforces Round 940 (Div. 2) and CodeCraft-23

2 days

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | ecnerwala | 3648 |

2 | Benq | 3580 |

3 | orzdevinwang | 3570 |

4 | cnnfls_csy | 3569 |

5 | Geothermal | 3568 |

6 | tourist | 3565 |

7 | maroonrk | 3530 |

8 | Radewoosh | 3520 |

9 | Um_nik | 3481 |

10 | jiangly | 3467 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 174 |

2 | awoo | 164 |

2 | adamant | 164 |

4 | TheScrasse | 159 |

4 | nor | 159 |

6 | maroonrk | 156 |

7 | -is-this-fft- | 150 |

8 | SecondThread | 147 |

9 | orz | 146 |

10 | pajenegod | 145 |

Hello there!

Today is Persian New Year's day, Nowruz!

I wish this year be an amazing year for you!

I hope to see all you in RED...

Hello everyone!

Today I'm going to talk you about a useful problem-solving method, **binary search**. If you have seen, in some problems we can't use an algorithm with $$$O(n^2)$$$ (because your program would be too slow to solve such problems). In those cases, you can use faster algorithms, but one of the popular algorithm is binary search. In binary search, you assume an integer as the answer, and you try that to see if it is the real answer or not. In this algorithm, you have an answer range, with usually starts with 0 and the end of the range will be maximum possible answer (i.g. 1e9). Let's play a game to understand better. One of your friends choose an integer from 1 to 100 and you need to ask some questions of your friend to find the number your friend had chosen. If you work smart (you will because you are smart) you start with this question: Is it less than 50? Do you agree if the friend's answer is yes, your range will be divided by 2 and also if your friend's answer is no. We assume he/she said NO, then you choose the number that is in the middle to work more efficiently, so you choose 25 and **until you trap 1 exact integer**, which is the answer!

Binary search is so similar to this game. You choose the middle integer in your **current** range, and check it. Let's calculate the order of algorithm. We assume you divide the range $$$x$$$ times, then $$$x$$$ would be $$$⌈log2(x)⌉$$$, because you it divides by 2 at most $$$⌈log2(x)⌉$$$ times! So the binary search is $$$O(⌈log(n)⌉)$$$.

Here's a simple code of binary search game:

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n; //assume we don't know the answer is n
int left = 1, middle, right = 101; //defining left and right of the range
while(left < right - 1) { //because our program does not check 101 and more!
middle = (left + right) / 2; //getting the middle of the current range
if (middle <= n) { //here is the question: is my guess less than the answer?
left = middle; //if yes, remove the left part of current range by moving the pointer
}
else {
right = middle; //and also similar thing for this
}
}
cout << "The answer is " << left; //finally we have found the exact answer
}
```

I explained the game in detail in the code comments ;)

Binary search is optimal algorithm to solve a lot of problems, so if you didn't know how to solve some problems **without** "Time limit exceeded", then try this!

Hope you enjoy my entry, please make me happy by clicking this little green button below :)

Thanks codeforces!

//This tutorial is just for begginers!

Happy New Year 2024 to all people around the world including Codeforces users! ;)

Please make me happy by giving me like on this entry <3 Thanks!

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/19/2024 08:20:13 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|