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
- 67467 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 is time complexity of bubble sort?
How long does it take to master data structures and algorithms?
Which interface provides the capability to store objects using a key-value pair?
Design a datastructure to represent the movement of a knight on a chess board
What is a height of a tree?
Differentiate between list and map.
What do you mean by sorting?
How to cut or remove an element from the array?
Define depth and height of a tree?
Define a binary tree?
Write a program to reverse a link list.
What is the purpose of sorting algorithms?
Windows 
