To illustrate, suppose I have column A with the numbers 1-16 listed in ascending order: (1,2,3,...); and column B with widget names; and I want to discover a certain widget by searching the numbers in column A. It's simple enough: =SEARCH(number;A1:A16;B1:B16). But suppose I have a list of 1600 sorted numbers and I need the widget name associated with entry 992. To get the necessary value, 'Search' would have to go through 992 iterations. A binary search, a la Java, would reduce it to about 10 iterations. But is that possible?
As far as I can tell, each cell in a spreadsheet is basically independent of all the others, and even organising a binary search "tree" inside a set of cells, as shown in
example, is fundamentally independent of all the others. Calc would want to go over each cell and compute its value depending on whatever formula the cell contains - even if the cell is unrelated to the search thread.Is it feasible to conduct a binary search?
I created a binary search tree within a LibreCalc sheet. Formally, the tree is as follows: I get something like this visually:
where (*) signifies the existence of 'hits' in the cell contents. However, LibreOffice Calc will elaborate all cells - say, A, A1, A2 - even if they are not on the search path, which passes through (B)-(B1).
