Interested to Buy Any Domain ? << Click Here >> for more details...
The element being searched for is not found in an array of
100 elements. What is the average number of comparisons
needed in a sequential search to determine that the element
is not there, if the elements are completely unordered?
- 11 Answers
- 35470 Views
- Morgan Stanley, Wipro, I also Faced
- E-Mail Answers
Answer Posted / tek002
The question is asking for the average number of
comparisons, not the particular realization... On average
you need 50 comparisons since the element you are searching
could just as likely be at the end of the array, as in the
beginning of the array. (for a brute force sequential
search)
If you really want to be fancy, you can actually do it with
10 (sqrt(N)) steps. Since a comparison search is an oracle
based search, you can implement the Grover's Algorithm
which is a unsorted database searching algorithm which is
the best known oracle based search for unsorted databases
(in fact is is provably the best oracle based search for
unsorted arrays).
| Is This Answer Correct ? | 3 Yes | 4 No |
Post New Answer View All Answers
What is sort function?
Which type of sorting is best?
Why is quicksort better than mergesort?
Compare Queue and Topic ?
When will we get ArrayStoreException?
What are the advantages and disadvantages of linked list over array?
Is array size dynamic or fixed?
How can avl tree be useful in all the operations as compared to binary search tree?
which notations are used in evaluation of arithmetic expressions using prefix and postfix forms?
How do you sort a list in reverse order?
What is example of data?
What will you prefer for traversing through a list of elements between singly and doubly linked lists?
Explain the expression trees?
What differences exist between hashmap and hashtable?
Is heap sort faster than quicksort?
