STARTING OUT WITH C++ MPL
STARTING OUT WITH C++ MPL
9th Edition
ISBN: 9780136673989
Author: GADDIS
Publisher: PEARSON
Expert Solution & Answer
Book Icon
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...

Blurred answer
Students 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.
There are benefits and drawbacks to using both sequential and binary search.
How should sequential and binary search methods be used?

Chapter 9 Solutions

STARTING OUT WITH C++ MPL

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
Background pattern image
Similar questions
SEE MORE QUESTIONS
Recommended textbooks for you
Text book image
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Text book image
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Text book image
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
Text book image
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Text book image
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Text book image
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education