CODEWITHSUNDEEP
rustslice
user9773683
user9773683

Reputation:

Is there an efficient function in Rust that finds the index of the first occurrence of a value in a sorted vector?

In [3, 2, 1, 1, 1, 0], if the value we are searching for is 1, then the function should return 2.

I found binary search, but it seems to return the last occurrence.

I do not want a function that iterates over the entire vector and matches one by one.

Upvotes: 12

Views: 6248

Answers (2)

duan
duan

Reputation: 8875

Since 1.52.0, [T] has the method partition_point to find the partition point with a predicate in O(log N) time.

In your case, it should be:

let xs = vec![3, 2, 1, 1, 1, 0];
let idx = xs.partition_point(|&a| a > 1);
if idx < xs.len() && xs[idx] == 1 {
    println!("Found first 1 idx: {}", idx);
}

Upvotes: 6

rodrigo
rodrigo

Reputation: 98486

binary_search assumes that the elements are sorted in less-to-greater order. Yours is reversed, so you can use 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());

Now, as you say, you do not get the first one. That is expected, for the binary search algorithm will select an arbitrary value equal to the one searched. From the docs:

If there are multiple matches, then any one of the matches could be returned.

That is easily solvable with a loop:

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;
   }
}

But if you expect many duplicates that may negate the advantages of the binary search.

If that is a problem for you, you can try to be smarter. For example, you can take advantage of this comment in the docs of binary_search:

If the value is not found then Result::Err is returned, containing the index where a matching element could be inserted while maintaining sorted order.

So to get the index of the first value with a 1 you look for an imaginary value just between 2 and 1 (remember that your array is reversed), something like 1.5. That can be done hacking a bit the comparison function:

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)
});

There is a handy function Ordering::then() that does exactly what we need (the Rust stdlib is amazingly complete).

Or you can use a simpler direct comparison:

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

The only detail left is that this function will always return Err(i), being i either the position of the first 1 or the position where the 1 would be if there are none. An extra comparison is necessary so solve this ambiguity:

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);
    }
}

Upvotes: 17

Related Questions