0
Which algorithm is efficient for finding an element from a sorted list?
Wiki User
∙ 6y ago
Basically you split the list in two, looking at the element in the middle of the list. If the list is in ascending order, and the element you are looking for is SMALLER than the element in the middle of the list, you repeat this procedure for the FIRST half of the list (again, splitting it in two); if it is LARGER, you repeat for the SECOND half of the list.
Wiki User
∙ 6y ago
Add your answer:
Earn +20 pts
What are the disadvantages of using a Binary Search?
The primary advantage of a binary search algorithm is that searching a sequence can be achieved in logarithmic time. The primary disadvantages are that the data must be in sorted order. Arrays are the ideal container for binary searches as they provide constant-time random-access and are therefore trivial to both sort and search efficiently. Sorted binary trees can also be used, however for optimal performance they must be totally balanced (e.g., red/black binary tree). Constant-time random-access is not a requirement of binary trees, however the cost of maintaining balance during construction of the tree has to be taken into account. With a linear search, we start at one end of the sequence and traverse through the sequence one element at a time until we find the value we're looking for, or we reach the element one-past-the-end of the sequence (in which case the element we're looking for does not exist). For a sequence of n elements, the worst case is O(n). Linear search is ideal for forward lists (singly-linked lists) and lists (doubly-linked lists) as neither provides nor requires constant-time random-access. With binary search, we locate the middle element in the sequence. If that's not the value we are looking for, we can easily determine which half of the sequence contains our value because the elements are in sorted order. So we eliminate the other half and repeat the algorithm with the remaining half. As such, each failure to find the value reduces the number of elements to be searched by half (plus the middle element). If there are no elements in the remaining half then the value does not exist. The worst case is therefore O(log n).
What is the time complexity of algorithm to solve fractional knapsack problem using greedy paradigm?
if the objects in the knapsack are already being sorted then it requires only O(n) times to arrange the objects...so total time require by the knapsack problem is T(n)=(nlogn) because sorting the objects require O(nlogn) time...Remaining is to run for n objects O(n). Hence, bounded by O(nlogn)
What are the examples of database?
A telephone directory. It has a bunch of information but it is all sorted efficiently to be able to find exactly what you need without having to read the whole phone book.
What is the difference between ascending and descending order?
Ascending means increasing (usually numbers but could be alphabetic). Descending is the opposite. 81, 121, 100, 169, 11, 9, 14; sorted in ascending order is: 9, 11, 14, 81, 100, 121, 169. The letters Q A B T U Y G H, sorted in descending order are: Y U T Q H G B A
What can you do in database?
A database is a program in which to store information. Such information can be sorted and manipulated to create reports, and aid an advertising mail-merge, and so on.
How do you search a particular element from the vector?
To search a particular element from the vector, use the find() algorithm. If the vector is sorted, you can use the binary_search() algorithm to improve efficiency. Both algorithms can be found in the <algorithm> header in the C++ standard library.
Which algorithm is more efficient- insertion sort algorithm or merge sort algorithm?
On average merge sort is more efficient however insertion sort could potentially be faster. As a result it depends how close to reverse order the data is. If it is likely to be mostly sorted, insertion sort is faster, if not, merge sort is faster.
Which search algorithm requires that the arrays contents be sorted?
Binary Search Algorithm
How do you know if an algorithm is effective?
If you mean "does what it is meant to do", you look for a mathematical or logical proof that the algorithm returns the correct answer over all possible inputs.If you mean "efficient", you do a simplified count of the number of operations it takes for the algorithm to complete and how it relates to the size of the input.Efficiency uses the notation O(n), where n is the size of the input. The O stands for "order of" to signify that we are not looking at exact counts, but an approximation.O(1) means that the running time of the algorithm is constant no matter how big the input is, this is as efficient it can get. An example is finding the maximum in a sorted list of numbers: The maximum will always be the last number in the list, so you don't even have to look at the rest of the numbers, and it doesn't matter how many of them there are.O(n) means that the running time increases linearly with the size of the input, which is reasonably efficient. An example is finding the maximum in an unordered list of numbers, it requires looking at every value exactly once.O(n*n) means that the running time increases with the square of the size of the input, which is less efficient. An example is comparing every element in a list to every other element in the list.When you have an efficiency analysis of the algorithm, you can compare it to the efficiency of other algorithms solving the same problem.See related links.
What is sub-algorithm?
It is an algorithm used by another algorithm as part of the second algorithm's operation.As an example, an algorithm for finding the median value in a list of numbers might include sorting the numbers as a sub-algorithm: There are plenty of algorithms for sorting, and the specifics of the sorting does not matter to the "median value" algorithm, only that the numbers are sorted when the sub-algorithm is done.For what an algorithm is, see related link.
Which one is the best and efficient sort?
There are a great many sorts, Mergesort and Quicksort being among the most popular. These both have on the order of n*log n expected case runtime, and while Quicksort can get as bad as n^2, this is unlikely due to most implementations using a random pivot. If you can make the assumption that ONLY NUMBERS will be sorted, you can use RadixSort, which is the fastest known sort for numbers. As for how to sort in particular programming languages, consult your local API (in C++ it is in the STL's "algorithm" include file).
What is the different sorting algorithms for arrays in java?
The built in array sorting algorithm (java.util.Arrays.sort) depends on the type of data being sorted. Primitive types are sorted with a modified implementation of quicksort. Objects are sorted with a modified implementation of mergesort.
What can matter be sorted by?
matter can be softed by its state in rtp. another way of sorting is element by element.
What is best algorithm for searching?
It depends on how the data is arranged. In case it is an array, use linear search or binary search or interpolation search according as the array is sorted or not and based on the distribution of data. If some other data structures are used (like heap) for making data retrieval efficient, other algorithms exist.
Write an algorithm to insert an item to a given location in sorted array?
To insert a number N into array A at index I: // Resize A if necessary If A is too small to add a new element then resize A // Right-shift all elements starting from position I For i = A.length to I A[i] = A[i - 1] // Insert new item A[I] = N
What are the advantages for bubble sort?
Bubble sort has no practical applications other than that it is often cited as an example of how not to write an algorithm. Insert sort is the best algorithm for sorting small lists of items and is often used in conjunction with quick sort to sort larger lists. Like insert sort, bubble sort is simple to implement and is a stable sort (equal items remain in the same order they were input). However, insert sort uses copy or move operations rather than swaps (which is actually three operations per swap) and is therefore quicker. The only time a bubble sort will work quicker than insert sort is when the array is already sorted, which renders the entire algorithm redundant. A modified algorithm that specifically tests if an array is sorted or not would be more efficient than a single-pass bubble sort.
When is it not recommended to perform the operation of binary search?
In computer science, a binary search or half-interval search algorithm finds the position of a specified value (the input "key") in an array sorted[1][2] into order on the values of the key. At each stage, the algorithm compares the sought key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index is returned. Otherwise, if the sought key is less than the middle element's key, then the algorithm repeats its action on the subarray to the left of the middle element or, if the input key is greater, on the subarray to the right. If the array span to be searched is reduced to zero, then the key cannot be found in the array and a special "Not found" indication is returned.A binary search halves the number of items to check with each iteration, so locating the an item (or determining its absence) takes logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.Next AnswerA binary search method requires that the list of items being search should be sorted in ascending (or descending) order. If the search list is not sorted, the binary search method will not work and other search methods will be needed.
