Fun with Flowcode - Binary Search
Posted: Mon Apr 20, 2026 1:20 pm
One common task for computers is searching data and retrieving values. Search is important - and returning a value often needs to be fast - equally determining that a value doesn't exist must be efficient too!
One useful algorithm for this purpose - is the binary search. This requires that the data is sorted - and here I use a simple insertion sort - and works by splitting the data into 2 halves - and comparing the search string to the middle point - deciding whether to search the 'upper' or 'lower' half. I use recursion - although an iterative algorithm is also possible.
This (very contrived) example - creates 5000 10 character strings. It then searches for each of these (- it 'knows' the location - so really the search is superfluous) - and should (does) find all of them. Then it searches for 5000 random strings - the probability is that none will be found.
Originally I stored a 'value' for each string - but to minimise the code I removed this - and BinarySearch just returns the location of the string (or -1) - this could be used to index am array of values if needed.
I missed a trick - the binary search could be modified slightly to find the insertion point for new data.
Typically - adding data is a less frequent (or one time) operation - and may be slower. I had to add a small delay to Generate to avoid WDT issues on esp32.
It is a MUCH quicker search algorithm than a linear search - which is left as an exercise
Note that it works in simulation but DOESN'T on esp32 - due to a bug in CAL_STRING.c. I patched this and it does work (satisfyingly quickly) on hardware.
*EDIT*
Now fixed - and an esp32 can search for 200000 random 10 character strings in <5s in a pool of 5000 (no WDT issues - but compiled optimised for performance). Not too shabby
Collectors of interesting error messages - I originally tried an array of 10000 - and I got, rather unexpectedly' - 'invalid initialiser' - for i in Generate ( = (0); ) - a memory issue for sure?
Martin
One useful algorithm for this purpose - is the binary search. This requires that the data is sorted - and here I use a simple insertion sort - and works by splitting the data into 2 halves - and comparing the search string to the middle point - deciding whether to search the 'upper' or 'lower' half. I use recursion - although an iterative algorithm is also possible.
This (very contrived) example - creates 5000 10 character strings. It then searches for each of these (- it 'knows' the location - so really the search is superfluous) - and should (does) find all of them. Then it searches for 5000 random strings - the probability is that none will be found.
Originally I stored a 'value' for each string - but to minimise the code I removed this - and BinarySearch just returns the location of the string (or -1) - this could be used to index am array of values if needed.
I missed a trick - the binary search could be modified slightly to find the insertion point for new data.
Typically - adding data is a less frequent (or one time) operation - and may be slower. I had to add a small delay to Generate to avoid WDT issues on esp32.
It is a MUCH quicker search algorithm than a linear search - which is left as an exercise
Note that it works in simulation but DOESN'T on esp32 - due to a bug in CAL_STRING.c. I patched this and it does work (satisfyingly quickly) on hardware.
*EDIT*
Now fixed - and an esp32 can search for 200000 random 10 character strings in <5s in a pool of 5000 (no WDT issues - but compiled optimised for performance). Not too shabby
Collectors of interesting error messages - I originally tried an array of 10000 - and I got, rather unexpectedly' - 'invalid initialiser' - for i in Generate ( = (0); ) - a memory issue for sure?
Martin
