2. In class, we discussed the problem of searching for an item x in a sorted...

Question

Question

2. In class, we discussed the problem of searching for an item x in a sorted array L with n entries. The returned value is su Below, you are given two algorithms for searching in a sorted array. Each function is a minor modification of the binary sear

engineering Computer-Science

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

(a) Decision Tree for Algorithm 1 is shown below:

5 (a)

(b) The Algorithm 1 is incorrect, because when the parameters first and last becomes equal, the algorithm directly returns -1 instead of comparing L[first] with x.

(c) Decision Tree for Algorithm 2 is shown below:

(©) 6 2 5 16 3 3

(d) The Algorithm 2 is also incorrect, because it runs into an infinite loop when the parameters first and last are equal.

// If you have any query do ask in the comments section.

Add a comment

Answer 2

Similar Homework Help Questions

1. Please write a Divide-and-Conquer Java algorithm solving the following problem: Given an "almost sorted" array...

1. Please write a Divide-and-Conquer Java algorithm solving the following problem: Given an "almost sorted" array of distinct integers, and an integer x, return the index of x in the array. If the element x is not present in the array, return -1. "Almost sorted" means the following. Assume you had a sorted array A[0…N], and then split it into two pieces A[0…M] and A[M+1…N], and move the second piece upfront to get the following: A[M+1]…A[N]A[0]…A[M]. Thus, the "almost sorted"...
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...
Question 3 Searching Algorithms [12 marks (4 marks) Define a method that when passed an array...

Question 3 Searching Algorithms [12 marks (4 marks) Define a method that when passed an array of integers arr and another integer target, returns the last index in arr where target exists and -1 if target isn't found in arr a. b. (4 marks) Provide a trace, in the form of a logic table, of running the following method for 1, 4, 4, 4, 5, 7, 8, 12, 12, 15, 16, 17, 35, 35, 35, 40 arr = target 14...

//Generic interface that describes various searching and sorting //algorithms. Note that the type parameter is unbounded....

//Generic interface that describes various searching and sorting //algorithms. Note that the type parameter is unbounded. However, //for these algorithms to work correctly, the data objects must //be compared using the method compareTo and equals. //In other words, the classes implementing the list objects //must implement the interface Comparable. The type parameter T //is unbounded because we would like to use these algorithms to //work on an array of objects as well as on objects of the classes //UnorderedArrayList and...
2. The following (adapted from Wikipedia) gives pseudocode for searching a sorted vector A for a ...

2. The following (adapted from Wikipedia) gives pseudocode for searching a sorted vector A for a specific element T. Given an array A of n elements with values or records A1 An and target value T, the following subroutine uses binary search to find the index of T in A. 1. Set L to 1 and R ton. 2. If L>R, the search terminates as unsuccessful Set m (the position of the middle element) to the floor of (L+R)/2. 3....
3. Write the function find sorted elt whose input is a vector sorted in increasing order...

3. Write the function find sorted elt whose input is a vector sorted in increasing order and an element x. The output is 0 if the element x does not occur in v, 1 if the element x does occur in v. Below is the algorithm you should implement, known as the binary search algorithm. Note that the code below returns the index, but we want to return true or false, not the index, so adjust your code accordingly. Algorithm....

Suppose you have a sorted array of positive and negative integers and would like to determine...

Suppose you have a sorted array of positive and negative integers and would like to determine if there exist some value of x such that both x and -x are in the array. Consider the following three algorithms: Algorithm #1: For each element in the array, do a sequential search to see if its negative is also in the array. Algorithm #2:For each element in the array, do a binary search to see if its negative is also in the...
Searching/sorting tasks and efficiency analysis - Binary Search Search for the character S using the binary...

Searching/sorting tasks and efficiency analysis - Binary Search Search for the character S using the binary search algorithm on the following array of characters: A E G K M O R S Z. For each iteration of binary search use a table similar to the table below to list: (a) the left index and (b) the right index of the array that denote the region of the array that is still being searched, (c) the middle point of the array,...
1. a. Using C++, represent the following graph using adjacency matrix, and implement depth first searching...

1. a. Using C++, represent the following graph using adjacency matrix, and implement depth first searching (DFS) by stack (define it with class) to traverse the graph. 6 7 2 4 b. If starting with node 2, when node 7 is printed, what numbers are in the stack (for DFS)? Please draw the stack step by step to show how the numbers are pushed into and popped out of it. 2. a. Given a set of integer numbers as int...

C++ Time the sequential search and the binary search methods several times each for randomly generated...

C++ Time the sequential search and the binary search methods several times each for randomly generated values, then record the results in a table. Do not time individual searches, but groups of them. For example, time 100 searches together or 1,000 searches together. Compare the running times of these two search methods that are obtained during the experiment. Regarding the efficiency of both search methods, what conclusion can be reached from this experiment? Both the table and your conclusions should...

2. In class, we discussed the problem of searching for an item x in a sorted...

Homework Answers

Add Answer to:
2. In class, we discussed the problem of searching for an item x in a sorted...

Post as a guest

Earn Coins

1. Please write a Divide-and-Conquer Java algorithm solving the following problem: Given an "almost sorted" array...

When binary searching a sorted array that contains more than one key equal to the search...

Question 3 Searching Algorithms [12 marks (4 marks) Define a method that when passed an array...

//Generic interface that describes various searching and sorting //algorithms. Note that the type parameter is unbounded....

2. The following (adapted from Wikipedia) gives pseudocode for searching a sorted vector A for a ...

3. Write the function find sorted elt whose input is a vector sorted in increasing order...

Suppose you have a sorted array of positive and negative integers and would like to determine...

Searching/sorting tasks and efficiency analysis - Binary Search Search for the character S using the binary...

1. a. Using C++, represent the following graph using adjacency matrix, and implement depth first searching...

C++ Time the sequential search and the binary search methods several times each for randomly generated...

2. In class, we discussed the problem of searching for an item x in a sorted...

Homework Answers

Add Answer to: 2. In class, we discussed the problem of searching for an item x in a sorted...

Post as a guest

Earn Coins

Add Answer to:
2. In class, we discussed the problem of searching for an item x in a sorted...