Rust：查找算法
查找算法是计算机科学中的一类重要算法，它可以帮助我们快速地在大量数据中查找特定的元素。常用的查找算法包括顺序查找、二分查找、插值查找、斐波那契查找、哈希查找、二叉查找树和红黑树等。
1 顺序查找
也叫线性查找，是最简单的一种查找方法。它的基本思想是从头到尾遍历整个数组，依次将扫描到的结点关键字与给定值k相比较，若相等则表示查找成功；若扫描结束仍没有找到关键字等于k的结点，表示查找失败。
顺序查找的时间复杂度为O(n)，空间复杂度为O(1)。
下面是一个简单的Rust代码示例，实现了顺序查找算法：
fn seq_search(arr: &[i32], value: i32) -> Option<usize> {
for (i, &item) in arr.iter().enumerate() {
if item == value {
return Some(i);
}
}
None
}
这段代码定义了一个名为seq_search的函数，它接受一个整数数组arr和一个要查找的整数value作为参数。函数内部使用了一个for循环来遍历整个数组，并使用enumerate()方法来获取每个元素的索引和值。如果当前元素的值等于要查找的值，则返回该元素的索引；如果遍历结束仍然没有找到，则返回None。
2 二分查找
也叫折半查找，是一种更高效的查找方法。它的基本思想是在有序数组中，取中间位置的元素与给定值进行比较，如果中间位置的元素大于给定值，则在数组的左半部分继续执行查找；如果中间位置的元素小于给定值，则在数组的右半部分继续执行查找；如果中间位置的元素等于给定值，则返回该元素的位置。
二分查找的时间复杂度为O(log2n)，空间复杂度为O(1)。
下面是一个简单的Rust代码示例，实现了二分查找算法：
fn binary_search(arr: &[i32], value: i32) -> Option<usize> {
let mut low = 0;
let mut high = arr.len() - 1;
while low <= high {
let mid = (low + high) / 2;
if arr[mid] == value {
return Some(mid);
} else if arr[mid] < value {
low = mid + 1;
} else {
high = mid - 1;
}
}
None
}
这段代码定义了一个名为binary_search的函数，它接受一个整数数组arr和一个要查找的整数value作为参数。函数内部定义了两个变量low和high来表示当前查找范围的下界和上界，并使用while循环来不断缩小查找范围。在每次循环中，都会计算出当前范围内部的中间位置mid，并将该位置上的元素与给定值进行比较。如果中间位置上的元素等于给定值，则返回该位置；如果中间位置上的元素小于给定值，则更新下界为mid + 1；如果中间位置上的元素大于给定值，则更新上界为mid - 1。如果循环结束仍然没有返回结果，则返回None。
3 插值查找
是二分查找是二分查找算法的改进，它根据数据分布，利用公式预测键值所在位置。插值查找的时间复杂度为O(log2(log2n))，空间复杂度为O(1)。
下面是一个简单的Rust代码示例，实现了插值查找算法：
fn interpolation_search(arr: &[i32], value: i32) -> Option<usize> {
let mut low = 0;
let mut high = arr.len() - 1;
while low <= high && value >= arr[low] && value <= arr[high] {
let mid = low + ((value - arr[low]) * (high as i32-low as i32) / (arr[high] - arr[low])) as usize;
if arr[mid] == value {
return Some(mid);
} else if arr[mid] < value {
low = mid + 1;
} else {
high = mid - 1;
}
}
None
}
这段代码定义了一个名为interpolation_search的函数，它接受一个整数数组arr和一个要查找的整数value作为参数。函数内部定义了两个变量low和high来表示当前查找范围的下界和上界，并使用while循环来不断缩小查找范围。
与二分查找不同的是，在每次循环中，都会根据给定值与当前范围内元素的大小关系，利用公式预测出键值所在位置mid，并将该位置上的元素与给定值进行比较。如果中间位置上的元素等于给定值，则返回该位置；如果中间位置上的元素小于给定值，则更新下界为mid + 1；如果中间位置上的元素大于给定值，则更新上界为mid - 1。如果循环结束仍然没有返回结果，则返回None。
4 斐波那契查找
是一种利用斐波那契数列进行查找的算法。它的时间复杂度为O(log2n)，空间复杂度为O(1)。
下面是一个简单的Rust代码示例，实现了斐波那契查找算法：
fn fibonacci_search(arr: &[i32], value: i32) -> Option<usize> {
let mut fib_m_minus_2 = 0;
let mut fib_m_minus_1 = 1;
let mut fib_m = fib_m_minus_2 + fib_m_minus_1;
while fib_m < arr.len() {
fib_m_minus_2 = fib_m_minus_1;
fib_m_minus_1 = fib_m;
fib_m = fib_m_minus_2 + fib_m_minus_1;
}
let mut offset = -1;
while fib_m > 1 {
let i = std::cmp::min(offset + fib_m_minus_2, arr.len() - 1);
if arr[i] < value {
fib_m = fib_m_minus_1;
fib_m_minus_1 = fib_m_minus_2;
fib_m_minus_2 = fib_m - fib_m_minus_1;
offset = i;
} else if arr[i] > value {
fib_m = fib_m_minus_2;
fib_m_minus_1 -= fib_m_minus_2;
fib_m_minus_2 = fib_m - fib_m_minus_1;
} else {
return Some(i);
}
}
if fib_m_minus_1 == 1 && arr[offset + 1] == value {
return Some(offset + 1);
}
None
}
这段代码定义了一个名为fibonacci_search的函数，它接受一个整数数组arr和一个要查找的整数value作为参数。函数内部首先使用while循环来计算出大于等于数组长度的最小斐波那契数，并记录下它前两个 斐波那契数。然后再使用while循环来不断缩小查找范围。在每次循环中，都会根据斐波那契数列的性质，计算出当前范围内的分割位置i，并将该位置上的元素与给定值进行比较。如果分割位置上的元素小于给定值，则更新下界为i；如果分割位置上的元素大于给定值，则更新上界为i；如果分割位置上的元素等于给定值，则返回该位置。如果循环结束仍然没有返回结果，则返回None。
5 哈希查找
是一种使用哈希函数来计算一个键值所对应的地址，进而建立哈希表格，然后利用哈希函数来查找各个键值存放在表格中的地址的算法。
它的时间复杂度为O(1)，空间复杂度为O(n)。
下面是一个简单的Rust代码示例，实现了哈希查找算法：
use std::collections::HashMap;
fn hash_search(arr: &[i32], value: i32) -> Option<usize> {
let mut hash_map = HashMap::new();
for (i, &item) in arr.iter().enumerate() {
hash_map.insert(item, i);
}
hash_map.get(&value).cloned()
}
这段代码定义了一个名为hash_search的函数，它接受一个整数数组arr和一个要查找的整数value作为参数。函数内部首先创建了一个哈希表，并使用for循环遍历整个数组，将每个元素的值和索引作为键值对插入到哈希表中。然后使用get()方法从哈希表中获取给定值对应的索引，并返回结果。
HashMap是一种哈希表，它实现了标准库中的std::collections::HashMap。它将键映射到值，可以快速查找、插入和删除键值对。
- HashMap的特点
- 键必须实现
Eq和Hashtrait。 - 值可以是任意类型。
- HashMap使用开放寻址法解决哈希冲突。
- 如何在Rust中创建和使用HashMap
use std::collections::HashMap;
fn main() {
let mut map = HashMap::new();
map.insert("key1", "value1");
map.insert("key2", "value2");
println!("{:?}", map);
let ret= map.get("key1");
println!("{:?}", ret);
}
- HashMap中常用的方法和操作
insert(key, value)：向HashMap中插入一个键值对。get(key)：根据键获取值。remove(key)：根据键删除键值对。contains_key(key)：检查HashMap是否包含指定的键。
- HashMap与其他数据结构的比较 与
BTreeMap相比，HashMap通常具有更快的查找、插入和删除速度，但它不保证元素的顺序。 - HashMap的应用实例
use std::collections::HashMap;
fn main() {
let mut map = HashMap::new();
map.insert("key1", "value1");
map.insert("key2", "value2");
if let Some(value) = map.get("key1") {
println!("The value of key1 is: {}", value);
} else {
println!("key1 is not in the map");
}
}
复制
- 总结 HashMap是一种非常有用的数据结构，它可以快速查找、插入和删除键值对。在Rust中，使用
std::collections::HashMap可以方便地创建和使用HashMap。
6二叉查找树
是一种特殊的二叉树，它具有以下性质：对于任意一个结点，它的左子树中所有结点的值都小于该结点的值，它的右子树中所有结点的值都大于该结点的值。二叉查找树可以用来实现高效地查找算法，其时间复杂度为O(log2n)。
下面是一个简单的Rust代码示例，实现了二叉查找树查找算法：
use std::cell::RefCell;
use std::rc::Rc;
type Tree = Option<Rc<RefCell<TreeNode>>>;
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
pub val: i32,
pub left: Tree,
pub right: Tree,
}
impl TreeNode {
#[inline]
pub fn new(val: i32) -> Self {
TreeNode {
val,
left: None,
right: None,
}
}
}
fn bst_search(root: &Tree, value: i32) -> bool {
if let Some(node) = root {
if node.borrow().val == value {
return true;
} else if node.borrow().val < value {
return bst_search(&node.borrow().right, value);
} else {
return bst_search(&node.borrow().left, value);
}
}
false
}
这段代码定义了一个名为bst_search的函数，它接受一个二叉查找树和一个要查找的整数value作为参数。函数内部使用if let语句来判断当前结点是否存在。如果当前结点存在，则将该结点上的元素与给定值进行比较。如果当前结点上的元素等于给定值，则返回true；如果当前结点上的元素小于给定值，则递归地在右子树中继续执行查找；如果当前结点上的元素大于给定值，则递归地在 左子树中继续执行查找。如果当前结点不存在，则返回false。
如何选择合适的查找算法
在选择查找算法时，需要根据数据的特点和查找需求来选择合适的算法。
- 如果数据是无序的，且数据量不大，可以使用顺序查找算法。
- 如果数据是有序的，且数据量较大，可以使用二分查找、插值查找或斐波那契查找算法。
- 如果数据分布比较均匀，可以使用插值查找算法。
- 如果需要快速地进行大量查找操作，可以使用哈希查找算法。
- 如果数据具有二叉查找树的性质，可以使用二叉查找树查找算法。
- from刘金，转载请注明原文链接。感谢！