bsutils

What this Does

If your sorted array/vec has duplicate items, a binary search will pick the desired item from an arbitrary index of that array. This crate provides you some utility functions, that will let you find the indexes where that item was first time or last time found in.

For one, see this sorted arry example:

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 to 6. If you precisely need to know the first/last (or both) index 6 was found in, this crate will be helpful for you.

Features

1. Support multiple types.
2. Clean and expressive code.
3. Time Complexity: O(logn), Space Complexity: O(1)

Version Note : Clarify description in README.md

How to use

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.

Quick Start

Find first index :

use bsutils::interface::find_first_idx;

fn main() {
	let list = [1, 1, 4, 6, 7, 7, 7, 7, 9, 9, 11];
	let given = 7; // the item we look for
	let first_idx = find_first_idx(&list, given);
	println!("{}", first_idx);

	// Output: 4
}

Find last index :

use bsutils::interface::find_last_idx;

fn main() {
	let list = [1, 1, 4, 6, 7, 7, 7, 7, 9, 9, 11];
	let given = 7; // the item we look for
	let last_idx = find_last_idx(&list, given);
	println!("{}", last_idx);

	// Output: 7
}

Find first & last both indexes :

use bsutils::interface::first_last_idxs;

fn main() {
	let list = [1, 1, 4, 6, 7, 7, 7, 7, 9, 9, 11];
	let given = 7; // the item we look for
	let both_idxs = first_last_idxs(&list, given);
	println!("{}", both_idxs);

	// Output: (4, 7)
}