如何对 Excel 范围执行二进制搜索以找到最后一个非空单元格？

Question

我有一个 Excel (.xlsx) 文件，该文件的第一列中只有数据。我的目标是找到包含数据的最后一行。现在，我正在逐个检查每个单元格（从第一行开始）看它是否为空。然而，Excel 查找相当昂贵——当有大约 10,000 个数据点时，查找最后一行需要十多秒。

我想进行平衡二分搜索而不是线性搜索。假设永远不会超过 100,000 行，但让我们看一个假设最多 15 行的较小示例。

假设最后一行是 11，则搜索路径如下所示：

Row 8 = filled, next search = 12
Row 12 = null, next search = 10
Row 10 = filled, next search = 11
Row 11 = child node, last data row found.

这需要 4 Excel 次读取（如果不包含 11 次则为 3 次，因为它是一个节点值），而如果搜索是线性的则需要 11 次。

这是 4 的相同内容。

Row 8 = null, next search = 4
Row 4 = filled, next search = 6
Row 6 = null, next search = 5
Row 5 = null & child node, last data row must be 4.

无论哪种方式，这都需要 4 Excel 次读取。但是，在最大行数为 100,000 的更大范围内，二分查找的平均执行时间会好得多。

谁能帮我用 C# 实现这种搜索？

我发现了这个问题，但我有兴趣在 C# 中找出这个算法，而不是使用 Excel 公式。

这是在 Microsoft.Office.Excel.Interop 中获取单元格值的语法：

string value = myWorksheet.Cells[3, 4].Text; // row 3, column 4

Answer 1

如果您知道最后可能的行，您可以运行对 excel 数据进行二进制搜索，如下所示：

var first = 0;
var last = 10000;
while (first+1 < last) {
    var mid = (first+last)/2;
    if (string.IsNullOrEmpty(myWorksheet.Cells[mid, 1].Text)) {
        last = mid;
    } else {
        first = mid;
    }
}

Demo.

如何对 Excel 范围执行二进制搜索以找到最后一个非空单元格？

How can I perform a binary search on an Excel range to find the last non-null cell?

c#

algorithm

binary-tree

excel-interop