Can someone please write a C++ code for this question using safe user IO, arrays, and dynamic memory?
Examine the two searching algorithms designed to search an array of numbers provided and provide written answers to the following questions.
Linear Search Algorithm
Initialise the starting index to 0
Initialise the current element as the array element at the starting index.
While the current index is less than the number of elements in the array
If the current element is the target, set found to true
Otherwise increment the current index
loop
Binary Search Algorithm
Initialise the high mark to the last element index of the array
Initialise the low mark to the first index of the array
While the high mark is greater than or equal to the low mark
Set the test index to the (high mark + low mark) / 2
If the element at the test index is the target
Set found to true and set the high mark to the current index -1, and low mark to the current index + 1
If the element is greater than the target
Set the high mark to the current index -1
If the element is less than the target
Set the low mark to the current index + 1
loop
(a) Which of the two algorithms requires greater prior processing of the input array? (and detail the prior processing required if any)
(b) Assuming any prior processing has been completed, which algorithm uses fewer comparisons (on average) to find the search target, or terminate the search?
(c) If both algorithms always had the same prior processing completed on the input array, is there a simple improvement which could be made to either, to improve its performance? (if so, detail the revised algorithm)
Linear Search Algorithm
Initialise the starting index to 0
Initialise the current element as the array element at the starting index.
While the current index is less than the number of elements in the array
If the current element is the target, set found to true
Otherwise increment the current index
loop
Binary Search Algorithm
Initialise the high mark to the last element index of the array
Initialise the low mark to the first index of the array
While the high mark is greater than or equal to the low mark
Set the test index to the (high mark + low mark) / 2
If the element at the test index is the target
Set found to true and set the high mark to the current index -1, and low mark to the current index + 1
If the element is greater than the target
Set the high mark to the current index -1
If the element is less than the target
Set the low mark to the current index + 1
loop
(a) Which of the two algorithms requires greater prior processing of the input array? (and detail the prior processing required if any)
(b) Assuming any prior processing has been completed, which algorithm uses fewer comparisons (on average) to find the search target, or terminate the search?
(c) If both algorithms always had the same prior processing completed on the input array, is there a simple improvement which could be made to either, to improve its performance? (if so, detail the revised algorithm)
Topic archived. No new replies allowed.