Rust 中是否有一个有效的函数可以找到一个值在排序向量中第一次出现的索引？

Question

在 中[3, 2, 1, 1, 1, 0]，如果我们要搜索的值是 1，那么函数应该返回 2。

我找到了binary search，但它似乎返回了最后一次出现。

我不想要一个遍历整个向量并一一匹配的函数。

Answer 1

binary_search假设元素按从小到大的顺序排序。你的反了，所以你可以使用binary_search_by：

let x = 1; //value to look for
let data = [3,2,1,1,1,0];
let idx = data.binary_search_by(|probe| probe.cmp(x).reverse());

现在，正如你所说，你没有得到第一个。这是预期的，因为二分搜索算法将选择一个与搜索到的值相等的任意值。从文档：

如果有多个匹配项，则可以返回任何匹配项。

这很容易用循环解决：

let mut idx = data.binary_search_by(|probe| probe.cmp(&x).reverse());
if let Ok(ref mut i) = idx {
   while x > 0 {
       if data[*i - 1] != x {
           break;
       }
       *i -= 1;
   }
}

但是，如果您期望可能会否定二分搜索的优势的许多重复项。

如果这对你来说是个问题，你可以尝试变得更聪明。例如，您可以利用以下文档中的此评论binary_search：

如果未找到该值，则Result::Err返回该值，其中包含可以在保持排序顺序的同时插入匹配元素的索引。

因此，要使用 a 获取第一个值的索引，1您可以在2和之间寻找一个虚值1（请记住，您的数组是颠倒的），例如1.5. 这可以通过修改比较函数来完成：

let mut idx = data.binary_search_by(|probe| {
    //the 1s in the slice are greater than the 1 in x
    probe.cmp(&x).reverse().then(std::cmp::Greater)
});

有一个方便的函数Ordering::then()可以满足我们的需求（Rust stdlib 非常完整）。

或者您可以使用更简单的直接比较：

let idx = data.binary_search_by(|probe| {
    use std::cmp::Ordering::*;
    if *probe > x { Less } else { Greater }
});

唯一的细节左边的是，这个函数总是返回Err(i)，作为i第一任的位置1或其中的位置1，如果有没有会。额外的比较是必要的，所以解决这个歧义：

if let Err(i) = idx {
    //beware! i may be 1 past the end of the slice
    if data.get(i) == Some(&x) {
        idx = Ok(i);
    }
}