CODEWITHSUNDEEP
arraystypescastingrust
the_lrner
the_lrner

Reputation: 655

Downcasting array length & indices

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

Upvotes: 0

Views: 86

Answers (1)

DK.
DK.

Reputation: 59005

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.

Upvotes: 7

Related Questions