How can I impl matrix find target

pub fn find_number_in2_d_array(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    let columnSize = matrix[0].len();
    let mut result: bool = false;
    for index in 0..matrix.len() {
        if (&matrix[index][0] <= &target && &matrix[index][columnSize - 1] >= &target) {
            result = binarySearch(&matrix[index], target);
            if (result) {
                return result;
            }
        }
    }
    return false;
}

fn binarySearch(array: &Vec<i32>, target: i32) -> bool {
    let mut startIndex: i32 = 0;
    let mut endIndex: i32 = (array.len() - 1) as i32;
    while startIndex <= endIndex {
        let mut mid: i32 = (startIndex + endIndex) / 2;
        if &target > array[mid] {
            startIndex = mid + 1;
        } else if &target < array[mid] {
            endIndex = mid - 1;
        } else {
            return true;
        }
    }
    return false;
}

Your binarySearch function doesn't compile because

  • you're trying to use an i32 as an index. Indexing with a Vec or a slice has to be done with a usize:
fn binarySearch(array: &Vec<i32>, target: i32) -> bool {
    let mut startIndex: usize = 0;
    let mut endIndex: usize = array.len() - 1;
    while startIndex <= endIndex {
        let mut mid: usize = (startIndex + endIndex) / 2;
        // --snip--
  • and you're comparing a reference, &i32 to a number i32. Remove the & from the target
-       if &target > array[mid] {
+       if target > array[mid] {
            startIndex = mid + 1;
-       } else if &target < array[mid] {
+       } else if target < array[mid] {
            endIndex = mid - 1;

You can also omit the explicit type declarations. Rust can infer that the type should be usize here.

The full binarySearch()
fn binarySearch(array: &Vec<i32>, target: i32) -> bool {
    let mut startIndex = 0;
    let mut endIndex = array.len() - 1;
    while startIndex <= endIndex {
        let mut mid = (startIndex + endIndex) / 2;
        if target > array[mid] {
            startIndex = mid + 1;
        } else if target < array[mid] {
            endIndex = mid - 1;
        } else {
            return true;
        }
    }
    return false;
}

There is a standard library function for binary searching, so you could remove the binarySearch function and instead do:

//--snip--
for index in 0..matrix.len() {
    if (&matrix[index][0] <= &target && &matrix[index][columnSize - 1] >= &target) {
-       result = binarySearch(&matrix[index], target);
+       result = matrix[index].binary_search(&target).is_ok();
        if (result) {
            //--snip--

Some other changes:

  • you can directly iterate over the elements instead of using an index in a for loop:
pub fn find_number_in2_d_array(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    let columnSize = matrix[0].len();
    let mut result: bool = false;
    for column in &matrix {
        if (column[0] < target && column[columnSize - 1] >= target) {
            result = column.binary_search(&target).is_ok();
            if (result) {
                return result;
            }
        }
    }
    return false;
}

Speaking of which, this if (column[0] < target && column[columnSize - 1] >= target) seems kind of pointless. This check isn't enough to know that the entire list is sorted. It only works if the list has 3 or less items.
You either know for sure in advance that the list is sorted, in which case you don't need to check if it's sorted, or you don't know for sure.
If you don't know, fully checking the list to make sure it's sorted defeats the point of binary searching. You might as well do a regular search:

pub fn find_number_in2_d_array(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    let mut result: bool = false;
    for column in &matrix {
        result = column.iter().find(|i| **i == target).is_some();
        if (result) {
            return result;
        }
    }
    return false;
}

You also don't really use this mutable result variable in any way other than to immediately return it, so we could get move it inside of the loop too:

pub fn find_number_in2_d_array(matrix: Vec<Vec<i32>>, target: i32) -> bool {
    for column in &matrix {
        let result = column.iter().find(|i| **i == target).is_some();
        if (result) {
            return result;
        }
    }
    return false;
}

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.