Binary search in microcontroller
The algorithm for binary search or search by division in half has been known for a long time. This article will consider an example of its “hardware” implementation on an 8-bit microcontroller and the features that arise in this case.
At one time, we released a simple cloud ACS controller for 100 users. It was based on the PIC18F46K22 microcontroller. As a memory for storing user key codes, we used a FLASH memory with an I^{2}With a capacity of 64 kB. The flash drive itself is quite fast, but on the I bus^{2}There was also a DS1307 clock chip, which operates at a speed not exceeding 100 kbps. We didn’t need a high speed of work, so in the end the entire bus was launched at a frequency of 100 kHz.
However, over time, we began to develop a new version of the controller, which already supports 3000 users. I didn’t want to change the architecture much, so the main nodes were preserved, but the amount of FLASH memory was increased to 256 kB.
And here an interesting moment arose. In the first version, the search for a key in memory was carried out by a simple enumeration of all 100 keys. This process took a fraction of a second and therefore no code optimizations were made. But with the number of 3000 entries, this time increased 30 times, which turned out to be unacceptable, since the user had an unpleasant delay between reading the card and opening the lock.
There are two ways to solve this problem. The first is the hardware version, which involves using a faster interface with a flash drive, for example, SPI. Reading speeds here are two orders of magnitude higher than when using I^{2}C. This is, so to speak, a head-on decision. The only inconvenience is that you have to put a new component into the device, redo the code and the printed circuit board. Plus, additional microcontroller lines will be required to connect such a memory chip.
But there is another way – software. It consists in altering the search procedure itself. Initially, it looked like this:
typedef struct
{
uint32_t COD;
uint8_t nSchedule;
} TSKUD_User;
bool skudFindUserByCode(uint32_t pCOD)
{
TSKUD_User user;
for (uint8_t i = 0; i < SKUD_USERS_COUNT; i++)
{
skudReadUser(i, &user);
if (user.COD == pCOD)
return 1;
}
return 0;
}
The skudReadUser function read a block of data from I^{2}From memory, then the code was checked for coincidence.
With a hundred users in the worst case (when the code was at the very end of the data array), the search time took about 0.1 sec. When switching to 3000 users, the time increased by 3 seconds!
Therefore, to speed up, the function was rewritten as follows:
bool skudFindUserByCode(uint32_t pCOD)
{
TSKUD_User user;
int16_t m, beg, end;
beg = 0;
end = SKUD_USERS_COUNT - 1;
while (beg <= end)
{
m = (beg + end) / 2;
skudReadUser(m, &user);
if (pCOD == user.COD)
return true;
if ((pCOD < user.COD) || (user.COD == 0))
end = m - 1;
else
beg = m + 1;
}
return false;
}
This is a classic version of the algorithm implementation, working on an ascending sorted data array. In our case, this is not a problem, since the data is loaded from the server, which sorts it before sending it to the controller.
You can read about various special cases when implementing binary search in the article: “I can’t write a binary search (https://habr.com/ru/post/146228)”.
So, let’s look at how the algorithm works. Variables beg and end set the starting and ending index of the data array. At each iteration, we calculate the index m, which is halfway between beg and end, and compare the required key value with what is at that index. In this case, three options are possible:
If the values match, then we have found the right key and you can open the lock.
If the number of the required card is less, then you should look for it in the left part of the array. Here we discard half of the obviously inappropriate options at once. The end index will now be m – 1.
If the number of the required card is less, then you should search for it in the right part of the array. We also discard half of the obviously inappropriate options at once, but change the beg index (it will be equal to m + 1).
If the data array does not contain the required key value at all, then we need to exit the loop. The exit condition is beg> end.
The additional condition user.COD == 0 in the line is very important:
if ((pCOD < user.COD) || (user.COD == 0))
The fact is that we simply fill in the unused elements of the data array with zeros. In reality, it happens like this. A sample of users sorted by the value of the map code is obtained from the database. This information is written to the data array, starting from index zero. The rest of the values are appended with zeros:
Index | Value |
0 | 1307131 |
one | 1308780 |
2 | 1318001 |
3 | 2174082 |
4 | 2290467 |
five | 2291521 |
… | 0 |
2996 | 0 |
2997 | 0 |
2998 | 0 |
2999 | 0 |
It would be possible to write the values 0xFFFFFFFF there, but we use it as a service one for the service needs of the system. Therefore, the additional condition user.COD == 0 always “forces” the algorithm to search for the code in the left half of the data array.
Someone might rightly point out that it makes no sense then to handle these null values at all. But the fact is that we do not transfer the actual number of access cards to the controller. Initially, for 100 maps, this did not make sense (the search was already very fast), and then we simply did not change the data structure. But, by and large, this is not necessary, since binary search speeds up the work very much.
Consider the following example. Suppose we have a complete array of 3000 records. The user brings the key and we have to check if there is such a card or not. In a linear search, we need to look at all records in the worst case. In total, 3000 comparisons will need to be made.
But with a binary search, the number of comparisons will be log_{2}3000 ≈ 11 pcs!
Interestingly, if there are as many as 4 billion records, then the number of comparisons when using binary search will increase to only 32!
Let’s try to check the binary search algorithm step by step on the above table. Let’s say we want to find the value of the key 2174082.
Iteration | beg | end | m | The code of the card you are looking for | Map code in the array at index m |
one | 0 | 2999 | 1499 | 2174082 | 0 |
2 | 0 | 1498 | 749 | 2174082 | 0 |
3 | 0 | 748 | 374 | 2174082 | 0 |
4 | 0 | 373 | 186 | 2174082 | 0 |
five | 0 | 185 | 92 | 2174082 | 0 |
6 | 0 | 91 | 45 | 2174082 | 0 |
7 | 0 | 44 | 22 | 2174082 | 0 |
8 | 0 | 21 | ten | 2174082 | 0 |
nine | 0 | nine | 4 | 2174082 | 2290467 |
ten | 0 | 3 | 2 | 2174082 | 1318001 |
eleven | 3 | 3 | 3 | 2174082 | 2174082 |
As a result, we found the desired value in 11 iterations. It is important to understand that 11 iterations is the maximum search time. In the above example, if we were looking for the value 2290467, then the number of iterations would be 9.
So what is the advantage of this solution? At the beginning of the article, I pointed out that the algorithm was implemented on a microcontroller. Using extremely cheap memory with interface I^{2}C lowers the total cost of the product, and the new search algorithm greatly reduces the controller response time.
It’s always interesting to see how the implementation of the algorithms works “live”. To do this, I shot two small videos showing the controller’s operation in two versions: with linear search and binary. I specially added the required value of the memory card to the very end of the list (index 2999), so that we could evaluate the work of both algorithms in the worst case.
Here’s how linear search works:
And here is the binary one:
The result, as they say, is obvious!