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, and (d) the character-to-character number of comparisons made during the search (line 09 of the Binary Search algorithm).
| Iteration | Left | Right | Middle | Number of Comparisons |
Binary Search
01 public static int binarySearch (int[] a, int target) {
02
03 int left = 0;
04 int right = a.length - 1;
05
06 while ( left <= right ) {
07
08 int middle = ( left + right ) / 2;
09 if ( a[middle] == target ) { // basic operation
10 return middle;
11 } else if ( target < a[middle] ) {
12 right = middle - 1;
13 } else {
14 left = middle + 1;
15 }
16 }
17 return -1; // target not found
18 }
Homework Answers
Add Answer to:
Searching/sorting tasks and efficiency analysis - Binary
Search
Search for the character S using the binary...
Problem 4: Sorting and Searching (55 points) a) (20 points) Scarch for the character K using...
Problem 4: Sorting and Searching (55 points) a) (20 points) Scarch for the character K using the binary search algorithm on the following array of characters: KM 2. R For each iteration of binary search use 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 index of the array, and (d) the number of character-to-character comparisons...
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...
6.) (a) A string contains several X's followed by several O's. Devise a divide-and-conquer algorithim that finds the number of X's in the string in log2n steps, where n is the length of th...
6.) (a) A string contains several X's followed by several O's. Devise a divide-and-conquer algorithim that finds the number of X's in the string in log2n steps, where n is the length of the string. (b) An array originally contained different numbers in ascending order but may have been subsequently rotated by a few positions. For example, the resulting array may be: 21 34 55 1 2 3 4 5 8 13 Is it possible to adapt the Binary Search...
Write a Java application that implements the recursive Binary Search alogrithm below: Write a Java application...
Write a Java application that implements the recursive Binary
Search alogrithm below:
Write a Java application that implements the recursive Binary Search alogrithm below:/** * Performs the standard binary search using two comparisons * per level. This is a driver that calls the recursive method * @return index where item is found or NOT FOUND if not found */public static <AnyType extends Comparable<? super AnyType>> int binarySearch(AnyType [] a, AnyType x) {return binarySearch(a, x, 0, a.length -1);}/** * Hidden recursive...
In C++, make the following binary search function work on an array of strings to give...
In C++, make the following binary search function work on an array of strings to give you the index location of the string you want in the array. It currently works on integers only. int binarySearch(int arr[], int firstIndex, int lastIndex, int target){ int index; if (firstIndex>lastIndex) index = -1; else { int mid = firstIndex + (lastIndex - firstIndex) / 2; if (target == arr[mid]) index = mid; else if (target < arr[mid]) index = binarySearch(arr, firstIndex, mid -...
//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...
Complete the binary search function. def binary Search (array, first, last, key): if last >= first:...
Complete the binary search function. def binary Search (array, first, last, key): if last >= first: mid = int(first + (last - first)/2) if array[mid] return mid key: elif array[mid] > key: ##Statement 1 else: ##Statement 2 else: return -1 Statement 1: return binarySearch(array, last, mid+1, key) Statement 2: return binarySearch(array, mid-1, first, key) Statement 1: return binarySearch(array, first, mid+1, key) Statement 2: return binarySearch(array, mid-1, last, key) Statement 1: return binarySearch(array, mid-1, first, key) Statement 2: return binary Search(array,...
6 (10 points Remember the recursive Searching algorithm Binary Search. Write a recursive method to search...
6 (10 points Remember the recursive Searching algorithm Binary Search. Write a recursive method to search for a target character in the array and return the index location if found or -1 if it is not found. 7 a5 points 17 points cach) Write the code to create a GUI based class Temperature Converter which inherits from JFrame and implements the ActionListerner interface. public static int binary Search(char target, char( theValues, int firstIndex, int lastindex) Example: Clicked "F to C"...
Searching/sorting tasks and efficiency analysis - Big-oh For each problem given below, do the following: 1....
Searching/sorting tasks and efficiency analysis - Big-oh For each problem given below, do the following: 1. Create an algorithm in pseudocode to solve the problem. 2. Identify the factors that would influence the running time of your algorithm. For example, if your algorithm is to search an array the factor that influences the running time is the array size. Assign names (such as n) to each factor. 3. Count the operations performed by the algorithm. Express the count as a...
Given the following code for a binary search, how many times this method have to be...
Given the following code for a binary search, how many times this method have to be executed in order to find the number 5? A) 1 time B) 2 times C) 3 times D) 4 times E) more than 5 times public class BinarySearch{ public static void main(String []args){ if (right >= left) { int middle = left + (right - left) / 2; if (arr[middle] == num) return middle; if (arr[mid] > num) return binarySearch(arr, left, middle - 1,...
Problem 4: Sorting and Searching (55 points) a) (20 points) Scarch for the character K using the binary search algorithm on the following array of characters: KM 2. R For each iteration of binary search use 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 index of the array, and (d) the number of character-to-character comparisons...
Write a Java application that implements the recursive Binary
Search alogrithm below:
Write a Java application that implements the recursive Binary Search alogrithm below:/** * Performs the standard binary search using two comparisons * per level. This is a driver that calls the recursive method * @return index where item is found or NOT FOUND if not found */public static <AnyType extends Comparable<? super AnyType>> int binarySearch(AnyType [] a, AnyType x) {return binarySearch(a, x, 0, a.length -1);}/** * Hidden recursive...
Complete the binary search function. def binary Search (array, first, last, key): if last >= first: mid = int(first + (last - first)/2) if array[mid] return mid key: elif array[mid] > key: ##Statement 1 else: ##Statement 2 else: return -1 Statement 1: return binarySearch(array, last, mid+1, key) Statement 2: return binarySearch(array, mid-1, first, key) Statement 1: return binarySearch(array, first, mid+1, key) Statement 2: return binarySearch(array, mid-1, last, key) Statement 1: return binarySearch(array, mid-1, first, key) Statement 2: return binary Search(array,...
6 (10 points Remember the recursive Searching algorithm Binary Search. Write a recursive method to search for a target character in the array and return the index location if found or -1 if it is not found. 7 a5 points 17 points cach) Write the code to create a GUI based class Temperature Converter which inherits from JFrame and implements the ActionListerner interface. public static int binary Search(char target, char( theValues, int firstIndex, int lastindex) Example: Clicked "F to C"...
Most questions answered within 3 hours.
-
Suppose your credit card balance is
$15,000
The minimum payment is
$313
and the annual percentage...
asked 9 seconds ago -
Question 1
a) Hydraulic conductivity of soils is an important parameter for
the design of engineering...
asked 2 minutes ago -
A solution containing 0.050 g of an unknown electrolyte in 2.50
g of cyclohexane was found...
asked 3 minutes ago -
Professor plays basketball and makes 75% of free
throws she shoots. If professor shot 5 free...
asked 3 minutes ago -
Create an ArrayListReview class with one generic type to do the
following
• Creates an array...
asked 36 minutes ago -
Two thermic power plants have the following marginal and total
cost of abatement of nitrogen oxide...
asked 35 minutes ago -
Which of the following statements does not correctly describe an
adjustment to net income when determining...
asked 49 minutes ago -
A sample of argon gas has a volume of 735 mL at a pressure of
1.20...
asked 45 minutes ago -
Write a Java program to find the perimeter of rectangle and ask
the user to input...
asked 1 hour ago -
what will be the effect of increasing the substrate
concentration in the presence of competitive inhibition?...
asked 1 hour ago -
Analyze the case Carpenter v. United States by the Kantianism
and Social Contract Theory, here is...
asked 1 hour ago -
The number of nonprofits operating in the United States today is
approximately:
3.5 million.
1.9 million....
asked 1 hour ago