Rust中binary_search方法无法找到数组内存在元素的问题

问题描述 #

刚接触Rust时，在&str类型数组上调用binary_search方法，无法找到数组中实际存在的元素，示例代码如下：

const CARDS_AS_STR: [&'static str; 52] = [
    "2c", "2d", "2h", "2s", "3c", "3d", "3h", "3s", "4c", "4d", "4h", "4s",
    "5c", "5d", "5h", "5s", "6c", "6d", "6h", "6s", "7c", "7d", "7h", "7s",
    "8c", "8d", "8h", "8s", "9c", "9d", "9h", "9s", "Tc", "Td", "Th", "Ts",
    "Jc", "Jd", "Jh", "Js", "Qc", "Qd", "Qh", "Qs", "Kc", "Kd", "Kh", "Ks",
    "Ac", "Ad", "Ah", "As",
];

fn main() {
    println!("{:?}", CARDS_AS_STR.binary_search(&"9c"));              // Ok(28)
    println!("{:?}", CARDS_AS_STR.binary_search(&"Kc"));              // Err(40) ?
    println!("{:?}", CARDS_AS_STR.binary_search(&CARDS_AS_STR[36]));  // Err(32) ?¿?
}

问题原因 #

binary_search的核心要求是：目标数组必须按照与搜索时相同的规则预先排序。这里的问题在于，字符串默认的排序是ASCII字典序，而手动定义的数组顺序并不符合这个规则：

• 在ASCII编码中，'A'（十进制65）的数值小于'K'（十进制75），所以字典序里"Ac"会排在"Kc"之前，但数组把"Ac"放在了最后。
• 这种数组顺序与binary_search依赖的默认排序规则不匹配，导致二分查找逻辑失效，无法定位到实际存在的元素。

解决方法 #

方法一：按默认字典序排序数组 #

将数组转换为可排序的容器（比如Vec），按字符串默认字典序排序后再执行binary_search：

const CARDS_AS_STR: [&'static str; 52] = [
    "2c", "2d", "2h", "2s", "3c", "3d", "3h", "3s", "4c", "4d", "4h", "4s",
    "5c", "5d", "5h", "5s", "6c", "6d", "6h", "6s", "7c", "7d", "7h", "7s",
    "8c", "8d", "8h", "8s", "9c", "9d", "9h", "9s", "Tc", "Td", "Th", "Ts",
    "Jc", "Jd", "Jh", "Js", "Qc", "Qd", "Qh", "Qs", "Kc", "Kd", "Kh", "Ks",
    "Ac", "Ad", "Ah", "As",
];

fn main() {
    let mut sorted_cards = CARDS_AS_STR.to_vec();
    sorted_cards.sort();

    println!("{:?}", sorted_cards.binary_search(&"9c"));              // Ok(28)
    println!("{:?}", sorted_cards.binary_search(&"Kc"));              // Ok(44)
    println!("{:?}", sorted_cards.binary_search(&CARDS_AS_STR[36]));  // Ok(36)
}

方法二：自定义比较规则 #

如果想保留原数组的牌面顺序（2、3...T、J、Q、K、A），可以使用binary_search_by，自定义基于牌面大小的比较逻辑：

const CARDS_AS_STR: [&'static str; 52] = [
    "2c", "2d", "2h", "2s", "3c", "3d", "3h", "3s", "4c", "4d", "4h", "4s",
    "5c", "5d", "5h", "5s", "6c", "6d", "6h", "6s", "7c", "7d", "7h", "7s",
    "8c", "8d", "8h", "8s", "9c", "9d", "9h", "9s", "Tc", "Td", "Th", "Ts",
    "Jc", "Jd", "Jh", "Js", "Qc", "Qd", "Qh", "Qs", "Kc", "Kd", "Kh", "Ks",
    "Ac", "Ad", "Ah", "As",
];

// 转换牌面为排序用的数值
fn card_rank(card: &&str) -> u8 {
    match card.chars().next().unwrap() {
        '2' => 2,
        '3' => 3,
        '4' => 4,
        '5' => 5,
        '6' => 6,
        '7' => 7,
        '8' => 8,
        '9' => 9,
        'T' => 10,
        'J' => 11,
        'Q' => 12,
        'K' => 13,
        'A' => 14,
        _ => 0,
    }
}

fn main() {
    println!("{:?}", CARDS_AS_STR.binary_search_by(|card| card_rank(card).cmp(&card_rank(&"9c"))));              // Ok(28)
    println!("{:?}", CARDS_AS_STR.binary_search_by(|card| card_rank(card).cmp(&card_rank(&"Kc"))));              // Ok(40)
    println!("{:?}", CARDS_AS_STR.binary_search_by(|card| card_rank(card).cmp(&card_rank(&CARDS_AS_STR[36]))));  // Ok(36)
}

内容的提问来源于stack exchange，提问作者zedryas