Answered: Use the binary search to find 8 from…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

discrete structures

Transcribed Image Text:## Binary Search Exercise ### Problem: 2. Use the binary search to find the number 8 from the following list: 1, 1, 5, 4, 7, 8, 9, 11, 13, 18, 19, 22, 22, 28, 32, 35, 40. **Note**: Show your steps. --- ### Explanation of Binary Search: Binary search is a very efficient algorithm for finding an item from a sorted list of items. It works by dividing the list in half with each pass until the desired item is found. 1. **Precondition**: The list must be sorted. 2. **Initialize**: - Start with two pointers: `low` (beginning of the list) and `high` (end of the list). 3. **Iteration**: - Calculate the `midpoint` by averaging `low` and `high`. - If the item at the `midpoint` is the target, return the index. - If the target is less than the item at `midpoint`, move the `high` pointer just before the `midpoint`. - If the target is greater, move the `low` pointer just after the `midpoint`. 4. **Repeat**: Continue the process until the `low` pointer is above the `high` pointer. __Steps for the given problem__: Given the list: 1, 1, 5, 4, 7, 8, 9, 11, 13, 18, 19, 22, 22, 28, 32, 35, 40 __1. Sort the list__: 1, 1, 4, 5, 7, 8, 9, 11, 13, 18, 19, 22, 22, 28, 32, 35, 40 __2. Set pointers__: - `low = 0` - `high = 16` (position of 40) __3. Calculate midpoint__: - Midpoint = (0 + 16) / 2 = position 8 (value is 13) __4. Compare mid value with target__: - 8 < 13, move `high` to `midpoint - 1` (position 7)

Expert Solution

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions