Lab: Binary Search
- Learn how to perform a binary search.
- Understand the running time of binary search as a function of the vector size.
Exercise 1: Binary search (10 points)
bool binarySearch(const vector<int> & v, int k);
Write a function called
that finds an occurrence of an integer
in a vector
v using binary search.
The function signature is given above.
Write your own implementation of binary search;
do not use the search function available in the C++ standard library.
Binary search assumes that the sequence of values
(stored in a vector in our case)
is either non-decreasing or non-increasing.
Assume that the vector passed into
is non-decreasing, which means that each value beyond the first
is either equal to or greater than the previous value.
Binary search is a natural search technique when the collection of items is stored in order. It is roughly the technique you would use to look up the meaning of a word in a dictionary or find a phone number in a telephone book.
Write test code that thoroughly tests your function. Express your tests using assertions.
Exercise 2: Finding the Maximum Value in a 2D Array (10 points)
const int ROWS = 4; const int COLS = 3; double findMax(duble a[ROWS][COLS]);
Implement a function called findMax that determines the maximum value in a 2-dimensional array. The declaration of the function is given above as well as the variables ROWS and COLS. Provide test code that defines an array of size ROWS by COLS and that uses an assert statement to check that the function returns the correct value.
Exercise 3: Linear Search (10 points)
int search(int a, int size, int k);
Implement a function that searches for a given value k in an array of integers. Do not assume the values are in order. If the value is found, the function returns the index of the value in the array; otherwise it returns -1. For example, for v = (-2, 4, 18, 6, -10) and k = 1, the function returns -1. and for k = 4 it returns 1. A declaration of the function is given above. Include test code with assertions.
Exercise 4: More Binary Search (10 points)
int binarySearch(int a, int size, int k);
Implement a function that uses binary search to find the index position of a given value k in an array of integers whose eements are in strictly increasing order. searches for a given value k in an array of integers. If the value is found, the function returns the index of the value in the array; otherwise it returns -1. For example, for v = (-2, 4, 5, 6, 8) and k = 1, the function returns -1. and for k = 4 it returns 1. A declaration of the function is given above. Include test code with assertions.
Exercise 5: Guess the Number Game (10 points)
Write a program that implements Guess-the-Number game. The program should enter a loop that starts by printing "What is the number?" After printing this, it reads the user response. (Use cin >> n to read the user response.) If the user enters a value less than 1023, the program prints "too small" and continues the loop. If the user enters a number larger than 1023, the program prints "too big" and continues the loop. If the user enters the number 1023, the program prints "you got it" and then terminates.