If your sorted array/vec has duplicate items, a binary search may pick the desired item from an arbitrary position of that array. This crate provide you some utility functions, that will let you know what was the first or last index that item was found in.
For one, see this sorted arry example:
rs
let arr = [1, 3, 4, 6, 6, 6, 6, 8, 12]
If we look up for the item 6, a simple binary search will return an index ranging 3~6. It can be 4 or 5. If you precisely need to know the first/last (or both) index 6 was found in, this crate will be helpful for you.
O(logn), Space Complexity: O(1)Version Note : Tidy codeblocks in README
This crate exports 3 functions, namely:
find_first_idx : Finds the index where the item was first found.
find_last_idx : Finds the index where the item was last found.
first_last_idx : Finds both indexes where the item was first and last found. Returns a tuple.
All of the 3 functions expects a ref to a sorted Array/Vector, and the item that you are looking for.
Find first index : ```rs use bsutils::interface::findfirstidx;
fn main() { let list = [1, 1, 4, 6, 7, 7, 7, 7, 9, 9, 11]; let given = 7; // the item we look for let firstidx = findfirstidx(&list, given); println!("{}", firstidx);
// Output: 4
}
**Find last index :**
rs
use bsutils::interface::findlastidx;
fn main() { let list = [1, 1, 4, 6, 7, 7, 7, 7, 9, 9, 11]; let given = 7; // the item we look for let lastidx = findlastidx(&list, given); println!("{}", lastidx);
// Output: 7
}
**Find first & last both indexes :**
rs
use bsutils::interface::firstlastidxs;
fn main() { let list = [1, 1, 4, 6, 7, 7, 7, 7, 9, 9, 11]; let given = 7; // the item we look for let bothidxs = firstlastidxs(&list, given); println!("{}", bothidxs);
// Output: (4, 7)
} ```