Explanation Given information: Suppose an array of length k is input to the while loop of the modified binary search algorithm. Proof: Let the input to the while-loop of the modified binary search algorithm contain k elements, thus a [ b o t ] , a [ b o t + 1 ] , ... , a [ t o p ] contains k elements. By the number of elements in a list theorem, we also know that the number of integers from bot to top top is top − bot + 1 and thus a [ b o t ] , a [ b o t + 1 ] , ... , a [ t o p ] contains top + bot − 1 element t o p + b o t − 1 = k We then assign mid to the upper of the two middle indices of the array. m i d = ⌈ b o t + t o p 2 ⌉ If a [ m i d ] ≠ x , then either a [ m i d ] < x or a [ m i d ] > x . FIRST CASE: a [ m i d ] < x If a [ m i d ] < x , then we assign mid − 1 to top and thus the input of the next iteration is then a [ b o t ] , a [ b o t + 1 ] , ... , a [ m i d − 1 ] . By the number of elements in a list theorem, we also know that the number of integers from bot to mid − 1 top is ( mid − 1) − bot + 1 = mid − bot and thus a [ b o t ] , a [ b o t + 1 ] , ... , a [ m i d − 1 ] contains mid − bot elements. Length array next iteration = mid − bot = ⌈ b o t + t o p 2 ⌉ − b o t = ⌈ k + 1 2 ⌉ − b o t t o p + b o t − 1 = k ≤ ⌈ k + 1 2 ⌉ − 1 as b o t ≥ 1 = ⌈ k + 1 2 − 1 ⌉ = ⌈ k + 1 − 2 2 ⌉ = ⌈ k − 1 2 ⌉ ⌈ k − 1 2 ⌉ = k 2 = ⌈ k 2 ⌉ = ⌊ k 2 ⌋ when k even and thus k − 1 odd ⌈ k − 1 2 ⌉ = k − 1 2 = ⌊ k 2 ⌋ when k odd and thus k − 1 even = ⌊ k 2 ⌋ SECOND CASE: a [ m i d ] > x If a [ m i d ] > x , then we assign mid + 1 to bot and thus the input of the next iteration is then a [ m i d + 1 ] , a [ m i d + 2 ] ,

5th Edition

ISBN: 9780357097717

Author: EPP

Publisher: CENGAGE L

See similar textbooks

Videos

Question

Chapter 11.5, Problem 18ES

To determine

Show that after one iteration of the loop, if a[mid]≠x, the input to the next iteration is an array of length at most ⌊k/2⌋.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 11.5, Problem 17ES

Chapter 11.5, Problem 19ES

Students have asked these similar questions

3. Consider the following regression model: Yi Bo+B1x1 + = ···· + ßpxip + Єi, i = 1, . . ., n, where are i.i.d. ~ N (0,0²). (i) Give the MLE of ẞ and σ², where ẞ = (Bo, B₁,..., Bp)T. (ii) Derive explicitly the expressions of AIC and BIC for the above linear regression model, based on their general formulae.

How does the width of prediction intervals for ARMA(p,q) models change as the forecast horizon increases? Grows to infinity at a square root rate Depends on the model parameters Converges to a fixed value Grows to infinity at a linear rate

Consider the AR(3) model X₁ = 0.6Xt-1 − 0.4Xt-2 +0.1Xt-3. What is the value of the PACF at lag 2? 0.6 Not enough information None of these values 0.1 -0.4 이

Chapter 11 Solutions

DISCRETE MATHEMATICS WITH APPLICATION (

Ch. 11.1 - If f is a real-valued function of a real variable,...Ch. 11.1 - Prob. 2TY Ch. 11.1 - Prob. 3TY Ch. 11.1 - Prob. 4TY Ch. 11.1 - Prob. 5TY Ch. 11.1 - Prob. 6TY Ch. 11.1 - Prob. 1ES Ch. 11.1 - The graph of a function g is shown below. a. Is...Ch. 11.1 - Prob. 3ES Ch. 11.1 - Sketch the graphs of the power functions p3 and p4...

Knowledge Booster

Learn more about

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

Show that after one iteration of the loop, if a [ m i d ] ≠ x , the input to the next iteration is an array of length at most ⌊ k / 2 ⌋ .

Solution Summary: The author illustrates how an array of length k is input to the while loop of the modified binary search algorithm.

Videos

Show that after one iteration of the loop, if a[mid]≠x, the input to the next iteration is an array of length at most ⌊k/2⌋.

Want to see the full answer?

Chapter 11 Solutions