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
- 66868 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 |
Why do we need arrays if all the operations that are performed on arrays can be performed on arraylist?
How does sort function work?
What should I learn first data structures or algorithms?
How would you use bsearch() function to search a name stored in array of pointers to string?
What is tree in computer science?
What is circular linked list?
What are the two traversal strategies used in traversing a graph?
Why do we need linked list?
write a program to accept name & sort them?
What are the operations that can be performed on a stack?
Define forest?
Does treemap preserve order?
Windows 
