list - 元素在列表中的位置 (OCaml)

Question

在 OCaml 的元素列表中获取元素位置的最快方法是什么？我知道如何获取列表中元素的“第 n 个”位置，但如果我已经知道该值，我想知道如何获取该元素的位置。

Answer 1

我相信最快的方法是最常用的方法：

1. 扫描列表
2. 如果您击中所需的元素，则返回位置
3. 如果从未命中，那么这是最坏的情况，并且会扫描整个列表。

时间复杂度为O(N)

let index_of e l = 
  let rec index_rec i = function
    | [] -> raise Not_found
    | hd::tl -> if hd = e then i else index_rec (i+1) tl
  in
  index_rec 0 l

Answer 2

let rec findi_rec base p l = match l with [] -> raise Not_found | h::_ when p h -> base | _::t -> findi_rec (base+1) p t;;

let findi p l = findi_rec 0 p l;;

作为：

# findi (fun x -> x=4) [1;9;3;2;1;4;5;7];;
- : int = 5