Detect impossible binary search comparison sequence

Q: Detect impossible binary search comparison sequence

This question evaluates understanding of binary search behavior and algorithmic reasoning about comparison order, search-space elimination, and invariants in sorted arrays.

Q: How do I approach Software Engineering Fundamentals interview questions?

Software Engineering Fundamentals questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master software engineering fundamentals interviews.

Question

Consider binary search on a sorted array of numeric keys. The following options list possible sequences of key values that the algorithm might compare against the search target (in order of comparisons).

Assume the keys 180, 200, 450, and 500 are in the array and are ordered so that 180 < 200 < 450 < 500.

Which of the following cannot be a sequence of keys compared during a single run of binary search (for some target value) on some sorted array?

Options:

A. 500, 200, 450, 180
B. 500, 450, 200, 180
C. 180, 500, 200, 450
D. 180, 200, 500, 450

Detect impossible binary search comparison sequence

Solution

Comments (0)

Detect impossible binary search comparison sequence

Overview

Solution

Comments (0)