Lesson test: Searching a sorted array

2.[2p]
What invariant does binary search maintain?

If the target is present at all, its index lies between lo and hi inclusive

Correct

The element at mid is always closer to the target than the endpoints

The answer is: If the target is present at all, its index lies between lo and hi inclusive

The interval always contains exactly half the remaining elements

The answer is: If the target is present at all, its index lies between lo and hi inclusive

lo is always less than the target and hi always greater

The answer is: If the target is present at all, its index lies between lo and hi inclusive

4.[3p]
The decision-tree lower bound for comparison-based search on $n$ elements is $⌈ \log_{2} (n + 1) ⌉$ because

the algorithm needs at least $n + 1$ distinct leaves, and a binary tree of height $h$ has at most $2^{h}$

Correct

every comparison halves the array

The answer is: the algorithm needs at least $n + 1$ distinct leaves, and a binary tree of height $h$ has at most $2^{h}$

the array must be sorted first

The answer is: the algorithm needs at least $n + 1$ distinct leaves, and a binary tree of height $h$ has at most $2^{h}$

$n + 1$ elements must each be compared once

The answer is: the algorithm needs at least $n + 1$ distinct leaves, and a binary tree of height $h$ has at most $2^{h}$

5.[2p]
Interpolation search can beat $\log_{2} n$ because

it uses the value of the key to guess a position, so the comparison lower bound does not apply to it

Correct

it makes two comparisons per round instead of one

The answer is: it uses the value of the key to guess a position, so the comparison lower bound does not apply to it

it does not require sorted data

The answer is: it uses the value of the key to guess a position, so the comparison lower bound does not apply to it

it has a better worst case than binary search

The answer is: it uses the value of the key to guess a position, so the comparison lower bound does not apply to it

6.[3p]
Why is $mid = lo + (hi - lo) / 2$ preferred to $(lo + hi) / 2$ ?

The sum can overflow a fixed-width integer, which shipped as a bug in Java's Arrays.binarySearch for nine years

Correct

It gives a different midpoint that converges faster

The answer is: The sum can overflow a fixed-width integer, which shipped as a bug in Java's Arrays.binarySearch for nine years

Division is cheaper on a subtraction

The answer is: The sum can overflow a fixed-width integer, which shipped as a bug in Java's Arrays.binarySearch for nine years

It handles unsorted arrays correctly

The answer is: The sum can overflow a fixed-width integer, which shipped as a bug in Java's Arrays.binarySearch for nine years

8.[2p]
Binary search on an array that is not sorted reports an error rather than a wrong answer.

True

The answer is: False

False

Correct

9.[3p]
Which are true of running binary search on a sorted linked list rather than a sorted array?

Select all that apply

Reaching the middle element costs $Θ (n)$ hops, destroying the saving

Correct

The total cost becomes $Θ (n)$

Correct

The ordering property still holds, so the halving argument is still valid

Correct

The comparison count rises to $Θ (n \log n)$

The answer is: Reaching the middle element costs $Θ (n)$ hops, destroying the saving, The total cost becomes $Θ (n)$ , The ordering property still holds, so the halving argument is still valid

Sign in

Searching a sorted array

1.[2p]
How many comparisons does binary search need in the worst case on an array of $10^{9}$ elements?

2.[2p]
What invariant does binary search maintain?

3.[3p]
Trace binary search for 13 in the array 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. How many comparisons does it make?

4.[3p]
The decision-tree lower bound for comparison-based search on $n$ elements is $⌈ \log_{2} (n + 1) ⌉$ because

5.[2p]
Interpolation search can beat $\log_{2} n$ because

6.[3p]
Why is $mid = lo + (hi - lo) / 2$ preferred to $(lo + hi) / 2$ ?

7.[2p]
In the array 2, 4, 4, 4, 7, 9, lower bound for 4 returns 1 and upper bound returns 4. What does the difference between them count?

8.[2p]
Binary search on an array that is not sorted reports an error rather than a wrong answer.

9.[3p]
Which are true of running binary search on a sorted linked list rather than a sorted array?

1.[2p] How many comparisons does binary search need in the worst case on an array of 109 elements?

2.[2p] What invariant does binary search maintain?

3.[3p] Trace binary search for 13 in the array 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. How many comparisons does it make?

4.[3p] The decision-tree lower bound for comparison-based search on n elements is ⌈log2(n+1)⌉ because

5.[2p] Interpolation search can beat log2n because

6.[3p] Why is mid=lo+(hi−lo)/2 preferred to (lo+hi)/2?

7.[2p] In the array 2, 4, 4, 4, 7, 9, lower bound for 4 returns 1 and upper bound returns 4. What does the difference between them count?

8.[2p] Binary search on an array that is not sorted reports an error rather than a wrong answer.

9.[3p] Which are true of running binary search on a sorted linked list rather than a sorted array?

1.[2p]
How many comparisons does binary search need in the worst case on an array of $10^{9}$ elements?

2.[2p]
What invariant does binary search maintain?

3.[3p]
Trace binary search for 13 in the array 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. How many comparisons does it make?

4.[3p]
The decision-tree lower bound for comparison-based search on $n$ elements is $⌈ \log_{2} (n + 1) ⌉$ because

5.[2p]
Interpolation search can beat $\log_{2} n$ because

6.[3p]
Why is $mid = lo + (hi - lo) / 2$ preferred to $(lo + hi) / 2$ ?

7.[2p]
In the array 2, 4, 4, 4, 7, 9, lower bound for 4 returns 1 and upper bound returns 4. What does the difference between them count?

8.[2p]
Binary search on an array that is not sorted reports an error rather than a wrong answer.

9.[3p]
Which are true of running binary search on a sorted linked list rather than a sorted array?