Binary Search
Suppose we want to check if a sorted sequence A contains an element v. For this, we can use Binary Search. Binary Search compares the value at the midpoint of the sequence A with v and eliminates half of the sequence from further consideration. The Binary Search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write a recurrence for the runningtime of Binary search and solve this recurrence.
Homework Answers
We know that binary search on a sorted array of size n takes O(log n) time....
We know that binary search on a sorted array of size n takes O(log n) time. Design a similar divide-and-conquer algorithm for searching in a sorted singly linked list of size n. Describe the steps of your algorithm in plain English. Write a recurrence equation for the runtime complexity. Solve the equation by the master theorem.
2) Write a recursive procedure in pseudocode to implement the binary search algorithm. 3) Explain, how...
2) Write a recursive procedure in pseudocode to implement the binary search algorithm. 3) Explain, how the binary search algorithm can be modified, or used, to insert, a new integer element x, into a sorted list of n intgers.
Binary Search (Ternary Search)
Ternary Search is a generalization of Binary Search that can be used to find an element in an array. Itdivides the array withnelements into three parts and determines, with two comparisons, which partmay contain the value we are searching for. For instance, initially, the array is divided into three thirdsby taking mid1=(n−1)/3 and mid2=((2(n−1))/3. Write a recurrence for the running time of Ternary Search and solve this recurrence.
Question 28 A binary search starts by comparing the search item to the first item in...
Question 28 A binary search starts by comparing the search item to the first item in the list. True False 1 points Question 29 The insertion sort algorithm sorts a list by repeatedly inserting an element in its proper place into a sorted sublist. True False 1 points Question 30 An interface is a class that contains only the method headings and each method heading is terminated with a semicolon. True False 1 points Question 31 Clicking on a JCheckBox...
I need question 9-10 answered. Thank you Question 1 iShow the resulting binary search tree if...
I need question 9-10 answered. Thank you
Question 1 iShow the resulting binary search tree if we are to insert following elements into the tree in given order, [34, 12, 23, 27,31,9,11,45, 20, 37. i) Show the resulting balanced binary search tree if we are to insert following sorted elements into the tree, [9,12,21, 23, 29, 31, 34, 45, 48, 52, 55] iii What is the pre-order traversal of the balanced binary search tree? v) What is the post-order traversal...
just explain it in english would be enough. modify the standard definition of a binary search...
just explain it in english would be enough.
modify the standard definition of a binary search tree to add a field N.size at each Suppose that we node, which records the size of the subtree under N'Tincluding N itself). A. Explain how to modify the procedure for adding both the case where X is not yet in the tree and is added, and the case where X is already in the tree, and the tree remains unchanged. element X to...
Suppose that, even unrealistically, we are to search a list of 700 million items using Binary...
Suppose that, even unrealistically, we are to search a list of
700 million items using Binary Search, Recursive (Algorithm 2.1).
What is the maximum number of comparisons that this algorithm must
perform before finding a given item or concluding that it is not in
the list
“Suppose that, in a divide-and-conquer algorithm, we always
divide an instance of size n of a problem into n subinstances of
size n/3, and the dividing and combining steps take linear time.
Write a...
The binary search algorithm from Chapter 9 is a very efficient algorithm for searching an ordered...
The binary search algorithm from Chapter 9 is a very efficient algorithm for searching an ordered list. The algorithm (in pseudocode) is as follows: highIndex - the maximum index of the part of the list being searched lowIndex - the minimum index of the part of the list being searched target -- the item being searched for //look in the middle middleIndex = (highIndex + lowIndex) / 2 if the list element at the middleIndex is the target return the...
When binary searching a sorted array that contains more than one key equal to the search...
When binary searching a sorted array that contains more than one
key equal to the search key, the client may want to know the index
of either the first or the last such key. Accordingly, implement
the following API: public class BinarySearchDeluxe { /* Returns the
index of the first key in a[] that equals the search key, or -1 if
no such key. */ public static int firstIndexOf(Key[] a, Key key,
Comparator comparator) /* Returns the index of the...
Write and test a function in C++ that uses the binary search algorithm to search an...
Write and test a function in C++ that uses the binary search algorithm to search an array of sorted strings – use a do..while loop to allow user to perform multiple searches w/o terminating the program – see sample output below. Use this name array: string names[SIZE] = { "Collins, Bill", "Smith, Bart", "Allen, Jim", "Griffin, Jim", "Stamey, Marty", "Rose, Geri", "Taylor, Terri", "Johnson, Jill", "Allison, Jeff", "Looney, Joe", "Wolfe, Bill", "James, Jean", "Weaver, Jim", "Pore, Bob",...
2) Write a recursive procedure in pseudocode to implement the binary search algorithm. 3) Explain, how the binary search algorithm can be modified, or used, to insert, a new integer element x, into a sorted list of n intgers.
I need question 9-10 answered. Thank you
Question 1 iShow the resulting binary search tree if we are to insert following elements into the tree in given order, [34, 12, 23, 27,31,9,11,45, 20, 37. i) Show the resulting balanced binary search tree if we are to insert following sorted elements into the tree, [9,12,21, 23, 29, 31, 34, 45, 48, 52, 55] iii What is the pre-order traversal of the balanced binary search tree? v) What is the post-order traversal...
just explain it in english would be enough.
modify the standard definition of a binary search tree to add a field N.size at each Suppose that we node, which records the size of the subtree under N'Tincluding N itself). A. Explain how to modify the procedure for adding both the case where X is not yet in the tree and is added, and the case where X is already in the tree, and the tree remains unchanged. element X to...
Suppose that, even unrealistically, we are to search a list of
700 million items using Binary Search, Recursive (Algorithm 2.1).
What is the maximum number of comparisons that this algorithm must
perform before finding a given item or concluding that it is not in
the list
“Suppose that, in a divide-and-conquer algorithm, we always
divide an instance of size n of a problem into n subinstances of
size n/3, and the dividing and combining steps take linear time.
Write a...
When binary searching a sorted array that contains more than one
key equal to the search key, the client may want to know the index
of either the first or the last such key. Accordingly, implement
the following API: public class BinarySearchDeluxe { /* Returns the
index of the first key in a[] that equals the search key, or -1 if
no such key. */ public static int firstIndexOf(Key[] a, Key key,
Comparator comparator) /* Returns the index of the...
Most questions answered within 3 hours.
-
During laser vision correction, a brief burst of 193 nm
ultraviolet light is projected onto the...
asked 28 minutes ago -
Use the sample data and confidence level given below to complete
parts (a) through (d).
A...
asked 30 minutes ago -
1 ) How well does the initial speed, v0,calculated from Equation
4 agree with the value...
asked 30 minutes ago -
1. What is the p-value for a right tail test for a single
proportion with a...
asked 1 hour ago -
A technician compares repair costs for two types of microwave
ovens (type I and type II)....
asked 44 minutes ago -
A certain statistical test is designed so that it fails 2% of
the time. Suppose that...
asked 45 minutes ago -
For the reaction: H2S(g) + 2H2O(l)3H2(g) + SO2(g) H° = 295 kJ
and S° = 295...
asked 1 hour ago -
The first-order reaction C4H8→2C2H4 has the reaction constant k
of 7.60×10−3 s−1. If the initial concentration...
asked 1 hour ago -
46.3 mL of a 0.0999 M solution of this acid (HOOC-(CH2)2-COOH)
is titrated to the equivalence...
asked 1 hour ago -
What is the difference between steady-state and equilibrium? Be
sure to include three properties of each...
asked 1 hour ago -
1..Research the microorganisms listed below. List the full
taxonomy (phylum, class, order, family, genus, species) of...
asked 1 hour ago -
1. What form of energy do cells rely on most to carry out
important processes?
2....
asked 1 hour ago