Interested to Buy Any Domain ? << Click Here >> for more details...
What is the average number of comparisons needed in a
sequential search to determine the position of an element in
an array of 100 elements, if the elements are ordered from
largest to smallest?
- 19 Answers
- 66271 Views
- ABB, SDE, I also Faced
- E-Mail Answers
Answers were Sorted based on User's Feedback
Answer / abhishek chakladar
though average number of comparison of sequential search is (N+1)/2 then in the question N=100 so that the answer will be (100+1)/2
=101/2
=50.5
| Is This Answer Correct ? | 1 Yes | 0 No |
Answer / ruchi baghel
it require n comparison where n=position of the element
if element is on 50th position
we just require 50 comparison bcz it is sequential search
one by one
| Is This Answer Correct ? | 1 Yes | 0 No |
Answer / gianni
sorry, the reduced formula should have been
n(1-p/2)+p/2
I forgot a space between the "to" and the "n"
| Is This Answer Correct ? | 0 Yes | 0 No |
Answer / ranjit
Gianni, Your answer would be correct if the list was unordered. Since it is a sorted list (descending order), one does not have to go through the whole list in order to determine that the element is not present. Thus, the problem is to simply traverse the list until you find a number <= the number, x, you are looking for. This can be done with (n+1)/2 comparisons on average. Probability of x being present in the list is not a factor.
Shyam, as I explained in the above para, the fact that the list is sorted is relevant. If it was unsorted, Gianni would be absolutely right.
| Is This Answer Correct ? | 0 Yes | 1 No |
Answer / gianni
the above answer of n+1/2 is correct if you assume it will
always be a successful search. you also need to take into
account the probability of the item NOT being in the list.
as such your final formula is actually
p/n * n(n+1)/2 + n(1-p) where p is the probability that the
item is in the list. That formula can be reduced ton(1-p/2)+p/2
assuming a probability of .5, you wind up with an answer of
(3n+1)/4 or ~3/4 of the list will be searched on average.
| Is This Answer Correct ? | 0 Yes | 2 No |
What sort does arrays sort use?
Define articulation point?
Define circular list?
Is bubble sort adaptive?
What are the objectives of studying data structures?
What is a binary search tree? Explain with example?
How do you do a selection sort?
Where is data structure used?
Is array static or dynamic?
Can we store null in arraylist?
What are hash tables good for?
where do you use double linked list?
Windows 
