# Problem 1 — Searching in an Ordered Vector

Download the file `code.zip`

and add its content (the files `search.cpp`

, `search.h`

, `car.cpp`

, `car.h`

, `test.cpp`

, `asserts.h`

) to a new Code::Blocks project.

In this problem, we want to implement different search algorithms for ordered vectors.

The elements we want to search are instances of the class `Car`

, which is defined in the files `car.h`

and `car.cpp`

. It is a simplified version of the class you implemented in Mini-Set 4. In particular, a car only contains its maximum speed and no other information Use the comparison operators defined for instances of the class `Car`

to implement your search algorithms.

## a — Linear Search

We start with a simple linear search.

Implement a linear search of `car`

in the vector of cars `vec`

in the function `linear_search`

in the file `search.cpp`

. This function should return `true`

if `car`

is in the vector and `false`

otherwise.

You can test your function by executing the program whose `main`

function is defined in the file `test.cpp`

.

## b — Binary Search

To improve the time complexity of our search, we will now use *binary* search.

Implement a *binary* search of `car`

in the vector of cars `vec`

in the function `binary_search`

in the file `search.cpp`

. This function should return `true`

if `car`

is in the vector and `false`

otherwise.

You can test your function by executing the program whose `main`

function is defined in the file `test.cpp`

.

## c — Binary Search of the First Index

We now want to know an *index* of the searched element in the vector. Because one element can appear multiple times in a vector, such an index is not necessarily unique. We will thus focus on the smallest index in the sequel.

Implement a *binary* search of `car`

in the vector of cars `vec`

in the function `binary_search_min`

in the file `search.cpp`

. This function should return the smallest index of occurrences of `car`

in the vector `vec`

, or `-1`

if `car`

does not occur in `vec`

.

You can test your function by executing the program whose `main`

function is defined in the file `test.cpp`

.

back to the course web site