0
Why is searching in a sorted list faster than searching in an unsorted list?
Wiki User
∙ 10y ago
With an unsorted list you have to search from the beginning to locate the item you're looking for. This is a linear search which takes linear time O(n) for n items. That is, the best case is constant time O(1) if the item you're looking for is the first item, it is O(n) if it is the last item (or the item doesn''t exist). Thus, on average, searches will take O(n/2) if the item exists, but always takes O(n) if it doesn't.
With a sorted list you start in the middle of the list. If the item you're looking for is less than this item, you can safely discard the upper half of the list but if it is greater you can discard the lower half. In other words you reduce the number of items to be searched by half. You then repeat the process with the remaining half. If the item you're looking for is equal to the middle item, you're done, but if the remaining half has no items the item does not exist. This is a logarithmic search with a best case of O(1), a worst case of O(log n) and an average case of O((log n)/2).
Logarithmic searches are clearly faster, on average, than linear searches. However, logarithmic searches require two separate comparison operations (equal to and less than) while linear searches require just one (equal to). Thus for a list of three or four items, a linear search is arguably quicker. But for larger lists, logarithmic search is quicker. Note that we don't need to test for greater than since it can be assumed that if an item is neither less than or equal to another item, then it must be greater.
Wiki User
∙ 10y ago
Add your answer:
Earn +20 pts
Write a c program to sort an unsorted stack?
A stack is implicitly sorted by hierarchical nested order. It does not make sense to sort a stack. Do you mean a list? If so, please ask the question again.
Insert in a sorted list?
Means to put a new item in the proper place in a sorted list.
Which is faster binary tree or binary search tree?
A tree doesn't do anything so it has no speed...
What advantages of a sorted list over a linked list?
All lists are linked lists; there is no such thing as a separate "sorted list". There are algorithms that can sort a list, of course, but they all work on linked lists.
What is an ordered list of data structure using c plus plus?
An ordered list of data in any programming language is simply a sorted array or list. In C++ this can either mean a sorted array, vector, list or forward list.
What is ordering in DBMS?
changing of unsorted list to sorted list in a ordering from alphabets, numbers, ASC/DESC.
It is pre requisite for binary search that the list should be in sorted order but if you have a unsorted list then which searching technique would be better binary search or linear search?
4 more info search how dangerous is the swine flu
What are the drawbacks of the binary search?
The only drawback I know of is that binary search requires that the list already be sorted. So if you have a really large unsorted list than binary search would not be the best option.
Write a c program to sort an unsorted stack?
A stack is implicitly sorted by hierarchical nested order. It does not make sense to sort a stack. Do you mean a list? If so, please ask the question again.
Insert in a sorted list?
Means to put a new item in the proper place in a sorted list.
If a list of words is sorted alphabetically in word then it is in blank order?
It will be sorted in ascending order.
Which is faster binary tree or binary search tree?
A tree doesn't do anything so it has no speed...
What advantages of a sorted list over a linked list?
All lists are linked lists; there is no such thing as a separate "sorted list". There are algorithms that can sort a list, of course, but they all work on linked lists.
Why is searching in a sorted list faster than searching in a unsorted list?
With an unsorted list you have to search from the beginning to locate the item you're looking for. This is a linear search which takes linear time O(n) for n items. That is, the best case is constant time O(1) if the item you're looking for is the first item, it is O(n) if it is the last item (or the item doesn''t exist). Thus, on average, searches will take O(n/2) if the item exists, but always takes O(n) if it doesn't. With a sorted list you start in the middle of the list. If the item you're looking for is less than this item, you can safely discard the upper half of the list but if it is greater you can discard the lower half. In other words you reduce the number of items to be searched by half. You then repeat the process with the remaining half. If the item you're looking for is equal to the middle item, you're done, but if the remaining half has no items the item does not exist. This is a logarithmic search with a best case of O(1), a worst case of O(log n) and an average case of O((log n)/2). Logarithmic searches are clearly faster, on average, than linear searches. However, logarithmic searches require two separate comparison operations (equal to and less than) while linear searches require just one (equal to). Thus for a list of three or four items, a linear search is arguably quicker. But for larger lists, logarithmic search is quicker. Note that we don't need to test for greater than since it can be assumed that if an item is neither less than or equal to another item, then it must be greater.
What is an ordered list of data structure using c plus plus?
An ordered list of data in any programming language is simply a sorted array or list. In C++ this can either mean a sorted array, vector, list or forward list.
Is duplicated data is accepted in linked list?
Yes definitely, a linked list can accept duplicate data. As the data of each node does not have any concern with data of other node. The node differs from each other in their addresses. Until user does not make the linked list to accept unique data, the linked list can accept duplicates. if unsorted (e.g. representig a queue): yes if sorted (e.g. representing a set): should be decided design-time
When google returns a list of websites how is the list sorted?
When Google returns a list of websites the list is sorted by which sites best match your criteria. What you enter into the search box determines what comes back on the list. At the top of the list you will find items that are most closely related to your search words.
