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。它将键映射到值，可以快速查找、插入和删除键值对。

1. HashMap的特点

• 键必须实现Eq和Hash trait。
• 值可以是任意类型。
• HashMap使用开放寻址法解决哈希冲突。

1. 如何在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);
}

1. HashMap中常用的方法和操作

• insert(key, value)：向HashMap中插入一个键值对。
• get(key)：根据键获取值。
• remove(key)：根据键删除键值对。
• contains_key(key)：检查HashMap是否包含指定的键。

1. HashMap与其他数据结构的比较 与BTreeMap相比，HashMap通常具有更快的查找、插入和删除速度，但它不保证元素的顺序。
2. 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");
    }
}

复制

1. 总结 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刘金，转载请注明原文链接。感谢！