Consider the following pseudocode for finding an element in a sorted array A[1..n]: 1: BINARY SEARCH(A[1..n],...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Consider the following pseudocode for finding an element in a sorted array A[1..n]: 1: BINARY SEARCH(A[1..n], x) 2: left = 1 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: right = n while (right left) mid=left + right-left 2 if x== A[mid] return mid else if x < A[mid] right mid-1 else if > A[mid] left = mid + 1 return NOTFOUND (a) State precisely the loop invariant for the while loop in lines 4-11 and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in Chapter 2 of CLRS. Conclude that if x is present in the sorted array A, correctly returns the index of z. (b) Prove by induction that the while loop in lines 4-11 will execute 1+log n times in the worst case. (Hint: observe what happens to the size of the subarray Alleft..right] after each iteration.) Conclude that the running time of the BINARYSEARCH algorithm is (logn). Consider the following pseudocode for finding an element in a sorted array A[1..n]: 1: BINARY SEARCH(A[1..n], x) 2: left = 1 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: right = n while (right left) mid=left + right-left 2 if x== A[mid] return mid else if x < A[mid] right mid-1 else if > A[mid] left = mid + 1 return NOTFOUND (a) State precisely the loop invariant for the while loop in lines 4-11 and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in Chapter 2 of CLRS. Conclude that if x is present in the sorted array A, correctly returns the index of z. (b) Prove by induction that the while loop in lines 4-11 will execute 1+log n times in the worst case. (Hint: observe what happens to the size of the subarray Alleft..right] after each iteration.) Conclude that the running time of the BINARYSEARCH algorithm is (logn).
Expert Answer:
Related Book For
Posted Date:
Students also viewed these programming questions
-
CANMNMM January of this year. (a) Each item will be held in a record. Describe all the data structures that must refer to these records to implement the required functionality. Describe all the...
-
Mary is 30 years old and married to Mark, age 36. Mark passed away on January 30, 2021. Mark was unemployed and had no income in 2021 due to his illness. Marys seven-year-old daughter, Jenny, lived...
-
Brand extension is a strategy of using a successful brand name to launch a new or modified product in a new product category. Identify a recent brand extension that you have seen and discuss the...
-
A liquid R-134a bottle has an internal volume of 0.0015 m3. Initially it contains 0.55 kg of R-134a (saturated mixture) at 26C. A valve is opened and R-134a vapor only (no liquid) is allowed to...
-
If the maximum anticipated hoist load is 12 kip, determine if the W8 \(\times 31\) wide-flange A-36 steel column is adequate for supporting the load. The hoist travels along the bottom flange of the...
-
Portias Parts Shop recorded the following purchases and sales during the past year: Assume that the company sold all of the June 15 purchase and 100 cases each from the January 1 beginning inventory,...
-
The management of Zigby Manufacturing prepared the following balance sheet for March 31. Cash Accounts receivable Raw materials inventory Assets Finished goods inventory Equipment Less: Accumulated...
-
Use the table below to answer the following questions: Labor Force of an Economy Labor Force Employed Structurally unemployed Cyclically unemployed Frictionally unemployed Number of People (millions)...
-
You are part of a strategic planning and marketing committee in a large health care system. You have been asked to make a presentation to the board of trustees because they are considering their...
-
Show how to compute the DFT of two even complex length- \(N\) sequences performing only one length \(N\) transform calculation. Follow the steps below: (i) Build the auxiliary sequence...
-
Given the DFT coefficients represented by the vector \[\mathbf{X}=\left[\begin{array}{llllllll}9 & 1 & 1 & 9 & 1 & 1 & 1 & 1\end{array} ight]^{\mathrm{T}}\] (a) determine its length-8 IDFT; (b)...
-
Show that \[\sum_{n=0}^{N-1} W_{N}^{n k}= \begin{cases}N, & \text { for } k=0, \pm N, \pm 2 N, \ldots \\ 0, & \text { otherwise }\end{cases}\]
-
Show that the PSD function of a WSS random process \(\{X\}\) satisfies the following properties: (a) \(\Gamma_{X}(0)=\sum_{v=-\infty}^{\infty} R_{X}(v)\). (b) It is an even function; that is:...
-
1. Arguing geometrically, find an eigenbsis for the reflection about the line in R? that is parallel to the vector
-
Let (X. A. p) be a measure space. Show that for any A,B A, we have the equality: (AUB)+(An B) = (A) + (B).
-
The relationship between the number of decibels and the intensity of a sound I (in watts per square meter) is = 10 log(I/1012). Find the intensity I for each decibel level (a) = 60 (b) = 135 (c)...
-
1. The graph of a polynomial function is ________, which means that the graph has no breaks, holes, or gaps. 2. The ________ ________ ________ is used to determine the left-hand and right-hand...
-
In Exercises 1-4, use a calculator to evaluate each function. Round your answers to four decimal places. (Be sure the calculator is in the correct mode.) 1. (a) sin 20.2 (b) csc 69.8 2. (a) tan 12.75...
-
What does it mean to say that the demand for resources is a derived demand? Is the demand for all goods and services a derived demand?
-
Using the data in exercise 2, determine how many units of resources the firm will want to acquire. Data from in exercise 2 Using the information in the following table, calculate the marginal revenue...
-
Using the information in the following table, calculate the marginal revenue product (MRP = MPP MR). Unit of Resources Total Resource Output Price Price 1 10 $5 $10 2 25 $5 $10 345 35 $5 $10 40 $5...
Study smarter with the SolutionInn App