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
- 66853 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 binary tree and its properties?
What is stack in geography?
Write a program for reversing the Single Linked List?
What are data and data types?
Why do we need sorting?
Which is the parent class of printerstatereasons class?
“int a[] = new int[3]{1, 2, 3}” – This a legal way of defining the arrays?
Why is hashmap used?
Why do we use a multidimensional array in data structure?
What is a static structure?
an array of size N in which every number is between 1 and N, determine if there are any duplicates in it. You are allowed to destroy the array if you like. [ I ended up giving about 4 or 5 different solutions for this, each supposedly better than the others ].
Is list same as array?
Windows 
