Part V Algorithm Analysis 1) Consider searching algorithms on the following arra
ID: 2968017 • Letter: P
Question
Part V Algorithm Analysis
1) Consider searching algorithms on the following array of data:
[22 ,21 ,9, 4 ,16, 2 ,10, 14 ,20 ,31 ,26 ,19 ,17, 28 ,8 ,13]
Suppose you want to implement a searching algorithm to see if the data set contains the number 19.
(a) Demonstrate (with diagrams like the ones I show in the live chats and in the Phase 5 PowerPoint Guide slides 11&12) how the search would go if you used:
Provide a THOROUGH demonstration using DIAGRAMS like the ones I use in the live chats of how a sequential search would go. Point deductions will apply if you do not use diagrams like like the ones I show in the live chats and in the Phase 5 PowerPoint Guide slides 11&12) (WORTH 8 points)
Provide a THOROUGH demonstration using DIAGRAMS like the ones I use in the live chats of how a binary search would go. Point deductions will apply if you do not use diagrams like like the ones I show in the live chats and in the Phase 5 PowerPoint Guide slides 11&12)
(WORTH 8 points)
PLACE YOUR DEMONSTRATION AND DIAGRAMS FOR THE BINARY SEARCH HERE.
(b) State the runtime for each of the searches, in this example, and for general data sets of size n. (and how you reached this run time). Show HOW you got this runtime. Give the runtime as a function and then as Big O.
State the SPECIFIC runtime of THIS sequential search. In other words, what is the exact numerical (number form) run time to find #19 in the given data array using a sequential search? Note, this is NOT Big-O, this will be a numerical value. (WORTH 7 points)
PLACE YOUR ANSWER HERE. The runtime is __________
State the GENERAL runtime of a sequential search for general data sets of size n. In other words, given a data array that has
Explanation / Answer
a) A sequential search
SOLUTION : Sequential Search goes from first number to the last number in order
Like for first Search it will compare 19 with 22 which will return a negative match so it will continue for comparing 19 with second element i.e. 21 and so on...
When it will be comparing with the Element number 12 than it will get a match for 19 inside the array so it will return the result as 12 which is the number of iterations taken to search the number 19 in the array. Number of iteration taken place is 12 to search 19 in the array.
A binary search
SOLUTION: For Binary Search we will have to first sort the Array because Binary search is always performed on the sorted array so Array after the sorting will become as follows:
[2 4 8 9 10 13 14 16 17 19 20 21 22 26 28 31]
The number of elements in the array is 16 so the Binary search starts with the mid point of the number of elements which is (end-base/2) = (16-1/2) ~ 8
So, It compares 8th elements i.e. 16 with 19 which is less than required match so we shift towards right making 9th elements the base and 16th elements the high elements and now the mid point is elements with value 21 which is now greater than 19 so we shift the high end to element 20 and perform the same again. This time mid element in sub section is 19 which is a match so Result is returned as 10 which is position of 19. Number of Iteration taken place is 3 to search 19 in the array.
b) Run time for Sequential search with data set of size n is n.
Run time for Binary Search with data set of size n is .
c) Issue of the order of the data in Binary Search:
For Binary search we always need the data set in sorted form because the concept of Binary search is to shift the searching array and narrow it to get to the data based on value of mid-value being greater or less than the search value.