Binary Search: A way to solve problems faster!

Правка en1, от MKasirloo, 2024-01-04 21:58:10

Binary Search

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:

C++ Code

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", the try this!

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

Thanks codeforces!

Теги binary search, algorithms

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский MKasirloo 2024-01-05 06:46:59 1 Tiny change: 'eded", the try this!' -> 'eded", then try this!'
en2 Английский MKasirloo 2024-01-04 22:00:12 42 Tiny change: 'odeforces!' -> 'odeforces!\n\n//This tutorial is just for begginers!'
en1 Английский MKasirloo 2024-01-04 21:58:10 2702 Initial revision (published)