Description
Write a C++ program to implement the Binary Search algorithm for searching a target element in a sorted vector. Your program should keep track of the number of comparisons used to find the target.
- To ensure the correctness of the algorithm the input data should be sorted in ascendingor descending order. An exception should be thrown when an input vector is unsorted.
- Test your program using vectors populated with consecutive (increasing or decreasing) integers in the ranges from 1 to powers of 2, that is, to these numbers:
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048.
Select the target as the last integer in the vector.
- Tabulate the number of comparisons to find the target in each range.
I get the same number of comparisons for the increasing or decreasing values because I created two different binary search algorithms for the increasing or decreasing case.
- Plot the number of comparisons to find a target where the vector size n = 2k, k = 1,2, . . . ,11 in each increasing/decreasing case. You can use any graphical package (including a spreadsheet).
.
(a) Provide a mathematical formula/function which takes n as an argument, where n is the vector size and returns as its value the number of comparisons.Does your formula match the computed output for a given input? Justify your answer.How can you modify your formula/function if the largest number in a vector is not anexact power of two? Test your program using input in ranges from 1 to 2k −1, k = 1,2,3, . . . ,11.
- Use Big-O asymptotic notation to classify this algorithm and justify your answer.
- Submit to CSNet an electronic copy of your code and results of all your experiments for grading.
- (R-4.7 p. 185) The number of operations executed by algorithms A and B is 8nlogn and 2n2, respectively. Determine n0 such that A is better than B for n ≥ n0.
- (R-4.21 p. 186) Bill has an algorithm, find2D, to find an element x in an n × narray A. The algorithm find2D iterates over the rows of A, and calls the algorithm arrayFind, of code fragment 4.5, on each row, until x is found or it has searched all rows of A. What is the worst-case running time of find2D in terms of n? What is the worst-case running time of find2D in terms of N, where N is the total size of A? Would it be correct to say thatfind2D is a linear-time algorithm? Why or why not?
- (R-4.39 p. 188) Al and Bob are arguing about their algorithms.Al claims his O(nlogn)time method is always faster than Bob’s O( n2)-time method. To settle the issue, they perform a set of experiments. To Al’s dismay, they find that if n < 100, the O(n2)-time algorithm runs faster, and only when n ≥100 then the O(nlogn)-time one is better. Explain how this is possible.
- Find the running time functions for the algorithms below and write their classification using Big-O asymptotic notation. The running time function should provide a formula on the number of operations performed on the variable s.
