STARTING OUT WITH C++ MPL
9th Edition
ISBN: 9780136673989
Author: GADDIS
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Expert Solution & Answer
Chapter 9, Problem 19RQE
Explanation of Solution
Linear search:
- Linear search or sequential search is the process of searching the particular element in the array one by one until the searching element is found.
- Here, it uses the loop iteration to start from the beginning of the array to the last element until it finds out the searching element.
- This searching process is continued till the last element until the searching element is found from the array.
- If the searching element is not present in the array, then the search process returns the message according to unsuccessful search.
Number of comparison in linear search:
To search the target element that is present in the array, the search element is compared with the number of elements present in the array. Even if the array contains 500 elements, the search process continues 500 times, if the search element is present at the end of the array.
Maximum number of comparison = N
Average number of the comparison = N / 2
Binary search:
- Binary search is a special search process that searches for the particular element present in the array. It starts searching from the middle towards the left or right until the search element is found.
- Initially from the given array, find out the middle element of the array and then check whether the middle element is larger or smaller than the searching element and continue the following steps based on the condition,
- If the search element is larger, it will search towards the right of the array.
- If the search element is smaller, it will search towards the left of the array.
- Since the searching process is continued either in left or right direction and it leaves any part of the array for comparison based on the condition satisfied...
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solutionStudents have asked these similar questions
Complete the following table by calculating the average and maximum number of comparisons the linear search will perform, and the maximum number of comparisons the binary search will perform.
How should sequential and binary search methods be used?
The efficiency of selection sort is not affected by the original order of the elements.
True
False
Chapter 9 Solutions
STARTING OUT WITH C++ MPL
Ch. 9.2 - Prob. 9.1CPCh. 9.2 - Prob. 9.2CPCh. 9.2 - Prob. 9.3CPCh. 9.2 - Prob. 9.4CPCh. 9.3 - True or false: Any sort can be modified to sort in...Ch. 9.3 - Prob. 9.6CPCh. 9.3 - Prob. 9.7CPCh. 9.3 - Prob. 9.8CPCh. 9.3 - Prob. 9.9CPCh. 9.6 - Prob. 9.10CP
Ch. 9.6 - Prob. 9.11CPCh. 9.6 - Prob. 9.12CPCh. 9.6 - Prob. 9.13CPCh. 9.6 - Prob. 9.14CPCh. 9.6 - Prob. 9.15CPCh. 9 - Prob. 1RQECh. 9 - Prob. 2RQECh. 9 - Prob. 3RQECh. 9 - Prob. 4RQECh. 9 - Prob. 5RQECh. 9 - Prob. 6RQECh. 9 - Prob. 7RQECh. 9 - A binary search will find the value it is looking...Ch. 9 - The maximum number of comparisons that a binary...Ch. 9 - Prob. 11RQECh. 9 - Prob. 12RQECh. 9 - Bubble sort places ______ number(s) in place on...Ch. 9 - Selection sort places ______ number(s) in place on...Ch. 9 - Prob. 15RQECh. 9 - Prob. 16RQECh. 9 - Why is selection sort more efficient than bubble...Ch. 9 - Prob. 18RQECh. 9 - Prob. 19RQECh. 9 - Prob. 20RQECh. 9 - Prob. 21RQECh. 9 - Charge Account Validation Write a program that...Ch. 9 - Lottery Winners A lottery ticket buyer purchases...Ch. 9 - Lottery Winners Modification Modify the program...Ch. 9 - Batting Averages Write a program that creates and...Ch. 9 - Hit the Slopes Write a program that can be used by...Ch. 9 - String Selection Sort Modify the selectionSort...Ch. 9 - Binary String Search Modify the binarySearch...Ch. 9 - Search Benchmarks Write a program that has at...Ch. 9 - Sorting Benchmarks Write a program that uses two...Ch. 9 - Sorting Orders Write a program that uses two...Ch. 9 - Ascending Circles Program 8-31 from Chapter 8...Ch. 9 - Modified Bin Manager Class Modify the BinManager...Ch. 9 - Using Files-Birthday List Write a program that...Ch. 9 - Prob. 14PCCh. 9 - Using Files-String Selection Sort Modification...Ch. 9 - Using Vectors String Selection Sort Modification...
Knowledge Booster
Similar questions
- Please explain the binary search. What is the best scenario for using a binary search?arrow_forwardGiven this array containing characters: Data В C F H J L M R S V X Z Index 1 3 4 5 7 8 9 10 11 12 13 List out the low, middle, and high indices for each pass when using binary search to locate the value 'Q' in the list. Use the following format for each pass needed: Pass: Low: Mid: High:arrow_forwardBinary search has several benefits over sequential search, but how do you choose which algorithm to use?arrow_forward
- Question in image Please explain how to do with the answer. Thank you.arrow_forwardQ#1: - If you have a matrix NxN+2, the user must enter NxN elements. The program has to implement the following: 1- Find the largest number in each row and then store it in the location before the last location of each row. 2-Find the smallest number in each row and then store it in the last location of each row.arrow_forwardQ2: How would you sort the array given below using quick sort algorithm? Trace the algorithm and show the array after each step. In every step, choose the first element as the pivotal. 1 3 4. 5n 7 20 50 10 90 40 30 80 70 60 O O Darrow_forward
- What are the binary search algorithm's sole requirements?arrow_forwardUse the main method as a driver to test your methods. To generate the weather for location at longitude -98.76 and latitude 26.70 for the month of February do: java WeatherGenerator111 -98.76 26.7O 3 public static void main (String[] args) { int number0fRows = 4001; // Total number of locations // Total number of 14 columns in file // File format: longitude, latitude, 12 months of transition probabilities int number0fColumns = 14; // Allocate and populate arrays that hold the transition probabilities double[][] drywet double[][] wetwet = new double[numberofRows ] [ numberOfColumns]; populateTransitionProbabilitiesArrays (drywet, wetwet, numberofRows); new double[number0fRows ] [numberOfColumns]; %D /*** WRITE YOUR CODE BELLOW THIS LINE. DO NOT erase any of the lines above. ***/ // Read command line inputs double longitute Double.parseDouble(args[0]); Double.parseDouble(args[1]); = Integer.parseInt(args[2]); double latitude %3D int month int[] forecast = oneMonthGenerator(longitute,…arrow_forwardLet N be an unordered array of integers. The maximum number of compares required to find the minimum value is N-1. [True/False]arrow_forward
- This is not a graded question so please don't disregard it as if it is. Thank you in advance professor!arrow_forwardIn every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray. Select one: True Falsearrow_forwardBest Partition You are given an array of positive numbers of size N and an integer K. You need to partition the array into K continuous segments. For each segment, the sum of its elements needs to be calculated. The segment with the minimum sum is called the bestSegment and the sum of the elements of the bestSegment is called the bestSum. For all possible combinations of partitions of the array when divided into K segments, their bestSum needs to be calculated and the one among them with maximum value needs to be returned. Input Specification: input1: an array of N positive numbers input2: an integer N denoting the length of the array input3: an integer K Output Specification: Return an integer denoting the maximum value of all possible bestSum. Example 1: input1: (1,2,3,4} input2: 4 input3: 2 Output: 4 Explanation: You can partition the given array into 2 continuous segments in the following manner- • 123 14- the sum of individual segments is (6,4) and the bestSum is 4 • 12134- the…arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
- Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill EducationStarting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSONDigital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
- C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSONDatabase Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage LearningProgrammable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education