Answered: Suppose we are performing a binary…

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

Suppose we are performing a binary search on a sorted vector initialized as follows:

// index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

vector<int>numbers {-5, -1, 0, 3, 9, 14, 19, 24, 33, 41, 56, 62, 70, 88, 99};

int index=binarySearch(numbers, 18);

Write the indexes of the elements that would be examined by the binary search (the mid values in our algorithm's code) and write the value that would be returned from the search.

please find : indexes examined

and value returned

Expert Solution

Explanation:

The binary search algorithm would work as follows:

Initialize start = 0, end = numbers.size()-1, and mid = (start + end) / 2 = 7
Compare numbers[mid] (24) with the target value (18), since 24 > 18, end = mid - 1 = 6
mid = (start + end) / 2 = 3, numbers[mid] (3) < 18, start = mid + 1 = 4
mid = (start + end) / 2 = 5, numbers[mid] (14) < 18, start = mid + 1 = 6
mid = (start + end) / 2 = 6, numbers[mid] (19) > 18, end = mid - 1 = 5
At this point, start > end, so the binary search terminates and returns -1, indicating that the target value was not found in the vector.

The elements examined by the binary search (in order) were: 24, 3, 14, 19.

The value returned by the search is -1.