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

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.

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

Why is selection sort more efficient than bubble sort on large arrays?

If an array is sorted in ________ order, the values are stored from highest to lowest.
See all solutions

Recommended explanations on Computer Science Textbooks

Computer Programming

Read Explanation

Data Representation in Computer Science

Read Explanation

Computer Systems

Read Explanation

Computer Organisation and Architecture

Read Explanation

Game Design in Computer Science

Read Explanation

Algorithms in Computer Science

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