Innodb-Binary Search algorithm

1. Background

* Binary Search (binary search), also known as half-and-half search, is used to find a record in an array of ordered records.

* the basic idea is to sort the records in order (increasing or decreasing)

* search in a jumping way during the search process.

two。 Advantages

* fewer comparisons

* Fast search speed

* good average performance

* take up less system memory

3. Shortcoming

* data sources must be orderly (increasing or decreasing)

* difficult to insert and delete

4. Examples

For example, for the ten numbers [5, 10, 19, 21, 31, 37, 42, 48, 50, 52], find 48 records, as shown in the figure

As can be seen from the picture, the number 48 was found three times.

If it is a sequential search, it will take 8 times.

Therefore, the efficiency of binary search method is better than that of sequential search method (on average).

The average number of sequential searches is: (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) / 10, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10, 10, 5, 5, 4, 5, 5, 6, 7, 8, 9, 10, 10, 5, 5, 5, 4, 5, 5, 6, 7, 8, 9, 10, 10, 5, 5, 5, 5, 6, 7, 8, 9, 10, 10, 5, 5, 5, 5, 6, 7, 8, 9, 10, 5.5.

The average number of binary searches is: (4, 3, 3, 4, 3, 1, 4, 3, 3, 2, 3) / 10 = 2.9.