arrays - 向下转换数组长度和索引

Question

我正在实现二进制搜索。该函数在数组中找到目标值时返回目标值的索引，否则返回-1。

我更喜欢处理 i32 而不是 usize 的索引，因为当目标是未找到。我明确地在函数的边缘进行转换，我认为这不是很好。什么是更 Rusty 的解决方法？

fn binary_search(nums: &[i32], target: i32) -> i32 {
    let num_size: i32 = nums.len() as i32;            // This seems bad
    bsearch(nums, target, 0, num_size as usize)
}

fn bsearch(nums: &[i32], target: i32, lo: usize, hi: usize) -> i32 {
    if hi < lo {
        return -1;
    }

    let mid_idx = lo + ((hi - lo) / 2);
    let guess = nums[mid_idx];

    if guess > target {
        bsearch(nums, target, lo, mid_idx - 1)
    } else if guess < target {
        bsearch(nums, target, mid_idx + 1, hi)
    } else {
        mid_idx as i32                      // This seems bad
    }
}

Answer 1

您不必要地与语言作斗争。 i32 不是数组索引的合适类型。相反，您应该使用 Option:

fn binary_search(nums: &[i32], target: i32) -> Option<usize> {
    let num_size = nums.len();
    bsearch(nums, target, 0, num_size)
}

fn bsearch(nums: &[i32], target: i32, lo: usize, hi: usize) -> Option<usize> {
    if hi < lo {
        return None;
    }

    let mid_idx = lo + ((hi - lo) / 2);
    let guess = nums[mid_idx];

    if guess > target {
        bsearch(nums, target, lo, mid_idx - 1)
    } else if guess < target {
        bsearch(nums, target, mid_idx + 1, hi)
    } else {
        Some(mid_idx)
    }
}

鉴于处理数组的函数必须对索引使用usize，强制它使用i32 没有任何好处。如果你想要i32因为你希望“not found”为-1，你可以在函数完成后执行转换。

---

注意:另外，请记住，在使用 i32 时，您确实应该进行边界检查。在 64 位系统上，数组长度可能大大超过 i32 可以表示的长度，即使在 32 位机器上，您也面临数组索引为负数的风险。