The element being searched for is not found in an array of
100 elements. What is the average number of comparisons
needed in a sequential search to determine that the element
is not there, if the elements are completely unordered?
Answers were Sorted based on User's Feedback
Answer / ntrphanikumar
100 comparisions
since element is not there and the data is unordered we need
to compare with each and every element
Is This Answer Correct ? | 46 Yes | 6 No |
Answer / tarzan
Answer i think is
u require 1,2,3,...,100(max) to search an element because it
is unsorted
i assume it to be random seq of number so we hav to search
until we find the required no
so if all input ie search request is a hit then avg is
50.5=~51 (1+2+..+100/(2*100))
and if search has misses den worst is de case i.e mean will
shift towards 100 but always less than 100 bcoz it is
unrealistic to say de search is alwayz miss
Is This Answer Correct ? | 23 Yes | 2 No |
we have to check all the elements of the array.so average is
n(size of array)
Is This Answer Correct ? | 14 Yes | 3 No |
Answer / poonam
IN sequential search (average case =[1/2(best case)+(wrost case)])...its the formula to calculate the average case of sequential search ...
so best case is when we found the element in first comparison.
worst case is when we found element in 100 comparison.
average case is =1/2(1+100)
ans would be 50.5
Is This Answer Correct ? | 11 Yes | 5 No |
Answer / tek002
The question is asking for the average number of
comparisons, not the particular realization... On average
you need 50 comparisons since the element you are searching
could just as likely be at the end of the array, as in the
beginning of the array. (for a brute force sequential
search)
If you really want to be fancy, you can actually do it with
10 (sqrt(N)) steps. Since a comparison search is an oracle
based search, you can implement the Grover's Algorithm
which is a unsorted database searching algorithm which is
the best known oracle based search for unsorted databases
(in fact is is provably the best oracle based search for
unsorted arrays).
Is This Answer Correct ? | 3 Yes | 4 No |
Answer / shailesh pratapwar
The avrage case complexity of any linear search alogrithm is
n/2.
So we need 50 comparisons to search in 100 elements.
Is This Answer Correct ? | 1 Yes | 2 No |
Answer / pankaj
(sum of all 1 to 100) - (sum of given numbers)= number missing
for this no comparison required
Is This Answer Correct ? | 4 Yes | 20 No |
What data structure underlies a python list?
Describe tree database. Explain its common uses.
Why do we need algorithm?
What is stack in geography?
What is an iterative algorithm?
What are the 4 types of data?
Which is better hashmap or arraylist?
List the basic operations carried out in a linked list?
What do you mean by 2-3-4 tree?
What is difference between array and arraylist?
What is advantage and disadvantage of linked list?
Model a data structure for a DFA that takes an event as parameter and performs a desired action.