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
- 66750 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 |
Briefly explain recursive algorithm?
Minimum number of queues needed to implement the priority queue?
State the advantages of using infix notations?
How to reverse a linked list iterative algorithm?
Describe the types of data structures?
List the area of applications of data structure.
Is a hashset ordered?
What are the 4 types of data?
How is the front of the queue calculated ?
Can list contain null values?
Differentiate between comparable and comparator.
What is binary tree example?
Windows 
