Question

In general, the binary search method needs no more than __________________ comparisons. A) [log2n]-1 B) [logn]+1...

In general, the binary search method needs no more than __________________ comparisons. A) [log2n]-1 B) [logn]+1 C) [log2n] D) [log2n]+1 Explain

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

Ans:[log2n]+1

The performance of binary search can be analyzed by viewing the run on a binary tree where root node is the middle element of the array. Left child node of the root is the middle element of the lower part and the right child node of the root is the middle element of the upper part.Starting from the root we traverse towards the left side or the right side depending on the key value(whether it is greater or less than the root node).

In the worst case binary search makes [log2n]+1 iterations because we know that the level of a tree is found by [log2n]+1.And worst case is reached when search reaches the last level of the tree.

we also know that the highest number of comparisons are done during the worst case only.Thus the answer would be [log2n]+1.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Select All true answers about linear and binary search 1. The advantage of linear search is...
Select All true answers about linear and binary search 1. The advantage of linear search is that it runs in O(1) space complexity and binary search can only run in O(logn) space complexity 2. The disadvantage of binary search is that it requires the container to be sorted which linear search does not. 3. The advantage of binary search over linear search is that is more efficient O(logn)versus O(n) average/worst case). 4. The advantage of linear search is that it...
Binary Search Tree. If best case is the number being searched for is root, O(1) or...
Binary Search Tree. If best case is the number being searched for is root, O(1) or O(log2^n), average case is O(logn), and worst case is O(n), what are some techniques for keeping the BST balanced so that the search will always be logarithmic?
Modify the binary search algorithm implemented in the search method of the HighArray class, to print...
Modify the binary search algorithm implemented in the search method of the HighArray class, to print a trace showing for each iteration of the search, the upper and lower limits of the search and the middle item selected in the binary split. The output might look something like this: Pass 1 left=0 right=9 pivot=4 Pass 2 left=0 right =3 pivot =1 Pass 3 left=2 right =3 pivot =2
Is searching an element in a Binary Search Tree (BST) faster than finding an element in...
Is searching an element in a Binary Search Tree (BST) faster than finding an element in a Binary Tree? If yes, explain why? (this is for Java programing)
State True or False. i) Binary search is used for searching in a sorted array. AND...
State True or False. i) Binary search is used for searching in a sorted array. AND ii) The time complexity of binary search is O(log n). A) True, False B) False, True C) False, False D) True, True Explain
Given a search problem where some elements are searched more than others, it is more important...
Given a search problem where some elements are searched more than others, it is more important to minimize the total cost of several searches rather than the worst-case cost of a single search. If x is a more frequent search target than y, building a tree where the depth of x is smaller than the depth of y will work better, even if that means increasing the overall depth of the tree. A perfectly balanced tree is not the best...
Which of the below is true about multiple comparisons? (There may be more than one true...
Which of the below is true about multiple comparisons? (There may be more than one true statment.) A. Multiple comparisons methods are only used if the null hypothesis of equality of population means is rejected. B. Multiple comparisons methods are only used if the null hypothesis of equality of population means is not rejected. C. Multiple comparisons are used when there are no upfront expectations or specific questions regarding the difference between group or population means. D. Multiple comparisons are...
Consider a binary search tree where each tree node v has a field v.sum which stores...
Consider a binary search tree where each tree node v has a field v.sum which stores the sum of all the keys in the subtree rooted at v. We wish to add an operation SumLE(K) to this binary search tree which returns the sum of all the keys in the tree whose values are less than or equal to K. (a) Describe an algorithm, SumLE(K), which returns the sum of all the keys in the tree whose values are less...
When using the comparative method (planned comparisons) to study why Red Phalaropes (a shorebird) lay unusually...
When using the comparative method (planned comparisons) to study why Red Phalaropes (a shorebird) lay unusually small eggs, the most useful data would come from: Select one: a. Wilson’s Phalaropes, a closely related species, which also lays small eggs. b. Tasmanian Galinules, a distantly related bird that lays small eggs. c. some closely related Phalarope species that lays large eggs. d. b and c are more useful than a.
This assignment involves using a binary search tree (BST) to keep track of all words in...
This assignment involves using a binary search tree (BST) to keep track of all words in a text document. It produces a cross-reference, or a concordance. This is very much like assignment 4, except that you must use a different data structure. You may use some of the code you wrote for that assignment, such as input parsing, for this one. Remember that in a binary search tree, the value to the left of the root is less than the...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT