Binary Search

Hello friends!

Following the series on basic search and sorting algorithms, in this article I will present you with the binary search algorithm.

In the previous article, we have learned about the sequential search algorithm, and it is really the simplest and slowest algorithm, but it is really the most chosen solution because it can solve any problem. search problem.

However, in the case of a given sequence of numbers, it makes no sense to traverse the sequence from beginning to end, since we can choose to browse more wisely. As I will show below.

Question

Given a sequence of numbers in ascending order of size

WOMEN WOMEN$N$ elements and number

X X$X$

X X$X$

Algorithm idea

This time, we will not go through the entire sequence of numbers anymore, but we will follow these steps:

1. Locate the middle of the sequence, call this value
   KY KY$K$ and this centered position is:m i d mid$mid$
2. If
   KY = X K = X$K=X$ , prove$m$ $i$ $d$ $mid$mi d is the location to look for (however, due to the requirement to determine the first location,$X$ $X$X appears, so we still have to search in the segment$[$ $l$ $e$ $f$ $t$ $,$ $m$ $i$ $d$ $-$ $first$ $]$ $[left,\; mid\; –\; 1]$[ l e f t , mi d − 1 ] see if there is another position equal to

   $X$ $X$X anymore).

3. If
   KY > X K gt X$K>X$ , prove$X$ $X$X if exists in the sequence, it will be in position from$[$ $l$ $e$ $f$ $t$ $,$ $m$ $i$ $d$ $-$ $first$ $]$ $[left,\; mid\; –\; 1]$[ l e f t , mi d − 1 ] (to the left of the number sequence).
4. If
   KY < X K lt X$K<X$ , show off$X$ $X$X if exists in the sequence, it will be in position from$[$ $m$ $i$ $d$ $+$ $first$ $,$ $r$ $i$ $g$ $H$ $t$ $]$ $[mid\; +\; 1,\; right]$[ mi d + 1 , r i g h t ] (to the right of the sequence).
5. Recall the search step corresponding to the location that
   X X$X$ may exist.

Note: Originally we can split the search as above because the sequence of numbers has an ascending order , if the sequence is unordered, you cannot search this way! But think of another way.

And here is the code that I prepared:

Full code you can see here: https://ideone.com/bebuntu

Complexity rating

It is easy to see that the complexity of the above algorithm is

O ( l o g WOMEN ) O(logN)$O(logN)$ , because each step of the search we split the sequence in half. This makes the search surprisingly faster.

And if you click on the full code link above, you will find this line in stdout

Total time for search: 0(s)

In the above code, I have given the value

X X$X$ to

10,000 won 10,000 won$\mathrm{10,000}$

1000 1000$1000$

Conclude

Above, I have presented you about Binary Search algorithm. This algorithm is really simple, but it is extremely effective for specific problems that have an ordered sequence of numbers (whether increasing or decreasing can be used).

Please memorize it to take advantage of it as soon as possible.

If you have any suggestions, please send a comment, I will reply and fix it for the next time.