Downcasting array length & indices

Question

I'm implementing binary search. The function returns the index of the target value when it's found in the array, otherwise -1.

I prefer to deal with indices that are i32 rather than usize as I need to allow negatives for returning -1 when the target is not found. I'm explicitly casting at the edges of the function, which I assume isn't great. What's a more Rusty way around this?

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
    }
}

You could also have looked at the [standard library implementation of `binary_search`](https://doc.rust-lang.org/std/primitive.slice.html#method.binary_search) to get a hint at what one idiomatic Rust way would be. — Shepmaster, Jan 30 '17 at 14:19

score 7 · Accepted Answer · edited Jan 30 '17 at 11:59

7

You're unnecessarily fighting the language. i32 isn't an appropriate type for array indices. Instead, you should use 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)
    }
}

Given that a function which deals with arrays has to use usize for indices, there's no benefit in forcing it to use i32 instead. If you want i32 because you want "not found" to be -1, you can perform the conversion after the function has finished.

Note: also, keep in mind that when using i32, you really should do bounds checking. On 64-bit systems, array lengths can greatly exceed what an i32 can represent, and even on 32-bit machines, you run the risk of having negative array indices.

edited Jan 30 '17 at 11:59

Matthieu M.

287,565
48
449
722

answered Jan 30 '17 at 07:36

DK.

55,277
5
189
162

I agree that `Option` is cleaner than a sentinel value, however I think the remark on size would be better off as a footnote. "*especially on 64-bit systems where array lengths can greatly exceed what an i32 can represent*" is in theory, but how often in practice do you deal with array of more than 2 billion elements? Apart from Zero-Sized Types, 2 billion elements is at least 2GB for the smallest possible element size (u8), and the size goes upward from there. Most software programs just don't have to deal with any collection that size, so putting the emphasis on it may weaken the answer. – Matthieu M. Jan 30 '17 at 10:24
@MatthieuM. I rephrased it a little, but I dunno how much more footnote-y it can get given that it's already the last paragraph. – DK. Jan 30 '17 at 10:31
I took a shot at it, feel free to revert if you don't like it. – Matthieu M. Jan 30 '17 at 12:00

Downcasting array length & indices

1 Answers1