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, 1/8 of the array will be left to search.

Step by step solution

01

Understanding Binary Search

In a binary search, we first sort the array in ascending order and then start by comparing the target value with the element in the middle of the array. If the target value is equal to this element, the search is successful. If the target value is less than the middle element, the search continues in the left half of the array; otherwise, the search continues in the right half of the array. With each comparison, the array search space is reduced by half.
02

Calculate the Remaining Array to Search

After each comparison in a binary search, half of the current array is eliminated from the search space. So, we need to calculate how much of the array is left after three comparisons. 1. After the first comparison: \\( \frac{1}{2} \cdot Original\_array\_size \\) 2. After the second comparison: \\( \frac{1}{2} \cdot \frac{1}{2} \cdot Original\_array\_size = \frac{1}{4} \cdot Original\_array\_size \\) 3. After the third comparison: \\( \frac{1}{2} \cdot \frac{1}{4} \cdot Original\_array\_size = \frac{1}{8} \cdot Original\_array\_size \\)
03

Final Answer

After three comparisons have been made in a binary search, only 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 steps sequentially through an array, comparing each item with the search value.

Assume that empName and empID are two parallel arrays of size numBmp that hold employee data. Write a pseudocode algorithm that sorts the emp ID 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].

The____________ search algorithm repeatedly divides the portion of an array being searched in half.

The maximum number of comparisons performed by linear search to find an item in an array of N elements is ___________.

The maximum number of comparisons that a binary search function will make when searching for a value in a 2,000 -clement array is ___________.
See all solutions

Recommended explanations on Computer Science Textbooks

Big Data

Read Explanation

Theory of Computation

Read Explanation

Algorithms in Computer Science

Read Explanation

Computer Programming

Read Explanation

Issues in Computer Science

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