# Searching in a vector

and program for linear and binary search in a vector Rust

## Introduction

Searching is finding the index of an element in a collection of elements. Here, in this article, we will discuss how to search for a given element in a vector.

We can search for an element in a vector ar an array in 2 possible ways

1. Linear Search : In this, we traverse through whole vector till the element is found. Hence, it takes O( n ) time complexity.
2. Binary Search : In this, we only check mid-points instead of checking the whole vector. Hence, it takes only O( log(n) ) time complexity. Vector must be sorted for Binary Search.

In the Linear Search, we traverse the whole vector, and check if the given element is equal to key. If the element is found, its index is returned.

As it traverses the whole array, it takes O( n ) time complexity.

Also, order of array does not matter for linear search. It is very simple to implement. Here is a simple function demonstrating Linear Search

```fn search(vecky:&Vec<usize>, key:usize) -> usize{    for i in 0..vecky.len() {        if vecky[i] == key {            return i;        }    }

Program With driver code

```fn search(vecky:&Vec<usize>, key:usize) -> usize{    for i in 0..vecky.len() {        if vecky[i] == key {            return i;        }    }
// Driver code
fn main() {    let vecky = vec![0, 1, 2, 3, 4, 5];    println!("{}", search(&vecky, 4) );    println!("{}", search(&vecky, 100) );}```

Output

4
6

Time Complexity : O( n )
Space Complexity : O( 1 )

The standard crate in Rust only has `binary_search()` and `contains()` function. So, you will have to make your own search function for Linear Search, as above

In the Binary Search, we only check the midpoints of a sorted list. Each time, we have to search only in half of the list. Hence, its complexity is O( log(n) ).

Also, the vector must be sorted for Binary search.

Here is the Algorithm

1. Calculate the mid-point of the sorted vector.
2. If the element is equal to the mid-point, return the index of the mid-point.
3. If the Element is greater than the mid-point, search for the element in the slice containing the larger values.
4. If the element is less than the mid-point, search the elements in slice containing smaller values than the mid-point.
5. Go back to step 2, till we have no elements left in the slice.

Note : If we observe carefully, each time if the element is not found, we have to find for the element in only the half of the vector. So, it takes only O ( log(n) ) for finding any element.

Here is the function for Binary Search in Rust

```fn binary_search(vecky:&Vec<usize>, key:usize) -> usize{    let mut low = 0;    let mut high = vecky.len()-1;
while low <= high {        let mid = low + (high - low) / 2;
// If key is middle element, return it        if vecky[mid] == key {            return mid;        }
// If key is greater than middle element, we ignore left half        if vecky[mid] < key {            low = mid + 1;        }
// If key is less than middle element, we ignore right half        else{            high = mid - 1;        }    }    // If the element is not found    return vecky.len();}```

Use the same driver code.

Output

4
6

Time Complexity : O( log(n) )
Space Complexity : O( 1 )

## binary_search() function

Rust already has `binary_search()` function built into it. It is already there in `std::vec::Vec` and hence, included in prelude. So, you don't even have to import it explicitly.

For example,

`fn main() {    let vecky = vec![0, 1, 2, 3, 4, 5];    println!("{}", vecky.binary_search(&4).expect("Not found") );    println!("{}", vecky.binary_search( &100).expect("Not Found") );}`

Output

4
Hence, you can easily use `binary_search()` function on any vector or a slice of vector in Rust.