M1103 Mini-Set 6

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.

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