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 aVec
or a slice has to be done with ausize
:
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 numberi32
. 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.