Log out Go to App
Go to App

Learning Materials

Features

Discover

Chapter 9: Problem 9

In a binary search, after three comparisons have been made, only ________ of the array will be left to search.

Short Answer

Expert verified
Answer: After three comparisons in a binary search, only 1/8 of the array will be left to search.

Step by step solution

01

Recall Binary Search Operation

In a binary search, the array must be sorted before starting the search process. During the search, the middle element is compared to the desired value. If the desired value equals the middle element, the search is successful. If it is less than the middle element, the search continues on the lower half of the array. If it is greater than the middle element, the search continues on the upper half of the array. After each comparison, the search space is reduced by half since the algorithm eliminates the part of the array that does not contain the desired value.
02

Perform First Comparison

After the first comparison is made, the search space is reduced by half. To know the remaining part of the array to search, we can represent this as a fraction: remaining part after 1st comparison is \(\frac{1}{2}\).
03

Perform Second Comparison

After the second comparison is made, the search space is reduced by half again. To know the remaining part of the array to search, we multiply the remaining part after the 1st comparison by \(\frac{1}{2}\): remaining part after 2nd comparison is \(\frac{1}{2} \times \frac{1}{2} = \frac{1}{4}\).
04

Perform Third Comparison

After the third comparison is made, the search space is reduced by half once more. To know the remaining part of the array to search, we multiply the remaining part after the 2nd comparison by \(\frac{1}{2}\): remaining part after 3rd comparison is \(\frac{1}{4} \times \frac{1}{2} = \frac{1}{8}\).
05

Conclusion

After three comparisons have been made in a binary search, only \(\frac{1}{8}\) of the array will be left to search.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

The _________ search algorithm requires that the array’s contents be sorted.

Bubble sort places ________ number(s) in place on each pass through the data.

Assume an array of structures is in order by the customerID field of the record, where customer IDs go from 101 to 500 . A) Write the most efficient pseudocode algorithm you can to find the record with a specific customerID if every single customer ID from 101 to 500 is used and the array has 400 elements. B) Write the most efficient pseudocode algorithm you can to find a record with a customer ID near the end of the IDs, say \(494,\) if not every single customer ID in the range of 101 to 500 is used and the array size is only 300 .

The _________ search algorithm steps sequentially through an array, comparing each item with the search value.

Assume that empName and empID are two parallel arrays of size numEmp that hold employee data. Write a pseudocode algorithm that sorts the empID array in ascending ID number order (using any sort you wish), such that the two arrays remain parallel. That is, after sorting, for all indexes in the arrays, empName [ index ] must still be the name of the employee whose ID is in empID [ index ].
See all solutions

Recommended explanations on Computer Science Textbooks

Functional Programming

Read Explanation

Data Representation in Computer Science

Read Explanation

Problem Solving Techniques

Read Explanation

Game Design in Computer Science

Read Explanation

Databases

Read Explanation

Data Structures

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free