F#中如何查找矩形二维数组中指定元素的索引？

好问题！在F#里处理二维数组的元素查找，确实和一维数组的findIndex思路略有不同，但我们可以基于类似的逻辑扩展，同时也能做到高效的实现。

1. 实现二维数组的元素索引查找 #

首先要区分两种常见的二维数组类型：数组的数组（'a[][]， jagged array）和矩形二维数组（'a[,]， rectangular array），两者的处理方式略有差异：

针对数组的数组（'a[][]） #

我们可以结合Array.mapi（带索引的遍历）和Array.tryFindIndex来实现，找到第一个匹配元素的行、列索引：

let findJaggedArrayIndex (target: 'a) (array: 'a[][]) =
    array
    |> Array.mapi (fun rowIdx row ->
        // 尝试在当前行中找到目标元素的列索引
        match row |> Array.tryFindIndex ((=) target) with
        | Some colIdx -> Some (rowIdx, colIdx)
        | None -> None)
    // 提取第一个找到的结果
    |> Array.tryFind Option.isSome
    |> Option.flatten

使用示例：

let jaggedArray = [|[|1;2;3|]; [|4;5;6|]; [|7;8;9|]|]
findJaggedArrayIndex 5 jaggedArray // 返回 Some (1, 1)

针对矩形二维数组（'a[,]） #

对于F#的矩形二维数组，我们可以用Array2D模块的函数，或者通过序列遍历实现：

let findRectArrayIndex (target: 'a) (array: 'a[,]) =
    array
    |> Array2D.mapi (fun rowIdx colIdx value ->
        if value = target then Some (rowIdx, colIdx) else None)
    // 将二维数组转为序列，筛选出第一个匹配的结果
    |> Seq.cast<Option<int * int>>
    |> Seq.tryFind Option.isSome
    |> Option.flatten

或者更直观的循环写法（性能和上面一致）：

let findRectArrayIndex (target: 'a) (array: 'a[,]) =
    let rowCount = Array2D.length1 array
    let colCount = Array2D.length2 array
    seq {
        for i in 0 .. rowCount - 1 do
            for j in 0 .. colCount - 1 do
                if array.[i, j] = target then
                    yield (i, j)
    }
    |> Seq.tryHead

使用示例：

let rectArray = array2D [[1;2;3]; [4;5;6]; [7;8;9]]
findRectArrayIndex 5 rectArray // 返回 Some (1, 1)

2. 关于效率：是否有比遍历更优的方法？ #

这里要分情况讨论：

• 如果你的二维数组是无序的：那没有办法比"找到第一个匹配就停止"的遍历更高效。因为元素的位置是随机的，最坏情况下必须检查所有元素才能确定不存在，但我们的实现会在找到第一个匹配时立即返回，已经是最优的了。
• 如果你的二维数组是有序的（比如每行递增、每列递增，或者整个数组按某种规则排序）：那可以用二分查找等优化算法，把时间复杂度从O(nm)降到O(log(nm))。但这种情况需要根据你的数组排序规则定制实现，没有通用的内置函数。

简单来说，对于普通的无序二维数组，我们上面的实现就是高效的——它不会遍历整个数组（除非元素在最后或不存在），而是找到目标就立即终止。

内容的提问来源于stack exchange，提问作者Code Guy