Answered: #### Part 1 Write a Python function…

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

#### Part 1

Write a Python function (`binary_search`) that implements the binary search algorithm.

This function will take a list argument (`values`), a value to search for (`to_find`), a start index (`start_index`), and an end index (`end_index`). The function will return `True` if `to_find` is present in `values`, and `False` otherwise.

Below, you will find some code to test your binary search:

```python

values = [2,4,6,8,10,12,14,16,18,20]

print(binary_search(values, 14, 0, len(values) - 1))

print(binary_search(values, 7, 0, len(values) - 1))

```

The output of the test code is below:

```

True

False

```

#### Part 2

Modify your `binary_search` function to count the number of comparisons (==, <, <=, >, or >=). The function will now return both the number of comparisons made and the `True` or `False` result.

The code below calls your function, and creates a simple ASCII bar chart of the number of comparisons (divided by 10, to account for small differences).

Some code to test your function has been provided, below:

```python

max_elements = 10000000

for length in range(1, max_elements, 500000):

values = list(range(1, (2 * length) + 1, 2))

num_comparisons, found = binary_search(values, length + 1, 0, len(values) - 1)

print(f'{length:08d}', '*' * (num_comparisons // 10))

```

The output of this test code has also been provided, below:

```

00000001

00500001 *****

01000001 *****

01500001 ******

02000001 ******

02500001 ******

03000001 ******

03500001 ******

04000001 ******

04500001 ******

05000001 ******

05500001 ******

06000001 ******

06500001 ******

07000001 ******

07500001 ******

08000001 ******

08500001 *******

09000001 *******

09500001 *******

```

Expert Solution

Step by step

Solved in 5 steps with 2 images

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