Apply algorithm 4.1.2 in P.140 with T=63, n=12 and A=(3,5,8,8,9,16,29,41,50,63,64,67). Draw the corresponding walkthrough as shown in P.140.
Apply algorithm 4.1.2 in P.140 with T=63, n=12 and A=(3,5,8,8,9,16,29,41,50,63,64,67). Draw the corresponding walkthrough as shown in P.140.
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
Related questions
Question
- Apply
algorithm 4.1.2 in P.140 with T=63, n=12 and A=(3,5,8,8,9,16,29,41,50,63,64,67). Draw the corresponding walkthrough as shown in P.140.
![Algorithm 4.1.2: Binary Search
Begin
p - 1;
q + n;
Repeat
j- [(p + q) /2];
If (A[j] < T) Then
p+j+1;
End;
If (A[j] > T) Then
q +j- 1;
End;
Until ( (A[j] = T) Or (p > q) );
If (A[j] = T) Then Output("T is A[", j, "]");
Else Output("T is not in A");
End;
End.
Walkthrough with n = 12 and A = (3, 5, 8, 8, 9, 16, 29, 41, 50, 63, 64, 67)
/| A[1] = 3,
/| A[7] = 29, A[8] = 41, A[9] = 50, A[10] = 63, A[11] = 64, &
A[6] = 16,
A[12] = 67
A[2] = 5,
A[3] = 8,
A[4] = 8,
A[5] = 9,
If T = 9, then
A[j]
relation
output
1
6
12
16
T<A[j]
1
3
5
8
A[j] < T
4
4
5
8
A[j] < T
5
9
A[j] = T
T is A[5]
If T = 64, then
A[j]
relation
output
1
6
12
16
A[j] < T
7
12
50
A[j] < T
10
11
12
64
A[j] = T
T is A[11]
If T = 23.4, then
/| T and the entries in A might be real numbers.
A[j]
relation
output
6
12
16
A[j] <T
7
12
50
T<A[j]
7
8
29
T<A[j]
7
T is not in A
/| T lies between A6 and A7.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F0f7775f3-edad-4f27-ba1b-f7886a7505bd%2F6f41df6c-13a0-4250-b344-65d29d1d24c7%2F609w4hf_processed.png&w=3840&q=75)
Transcribed Image Text:Algorithm 4.1.2: Binary Search
Begin
p - 1;
q + n;
Repeat
j- [(p + q) /2];
If (A[j] < T) Then
p+j+1;
End;
If (A[j] > T) Then
q +j- 1;
End;
Until ( (A[j] = T) Or (p > q) );
If (A[j] = T) Then Output("T is A[", j, "]");
Else Output("T is not in A");
End;
End.
Walkthrough with n = 12 and A = (3, 5, 8, 8, 9, 16, 29, 41, 50, 63, 64, 67)
/| A[1] = 3,
/| A[7] = 29, A[8] = 41, A[9] = 50, A[10] = 63, A[11] = 64, &
A[6] = 16,
A[12] = 67
A[2] = 5,
A[3] = 8,
A[4] = 8,
A[5] = 9,
If T = 9, then
A[j]
relation
output
1
6
12
16
T<A[j]
1
3
5
8
A[j] < T
4
4
5
8
A[j] < T
5
9
A[j] = T
T is A[5]
If T = 64, then
A[j]
relation
output
1
6
12
16
A[j] < T
7
12
50
A[j] < T
10
11
12
64
A[j] = T
T is A[11]
If T = 23.4, then
/| T and the entries in A might be real numbers.
A[j]
relation
output
6
12
16
A[j] <T
7
12
50
T<A[j]
7
8
29
T<A[j]
7
T is not in A
/| T lies between A6 and A7.
![If T = 99, then
A[j]
relation
output
12
16
A[j] < T
9
12
50
A[j] < T
10
11
12
64
A[j] < T
12
12
12
67
A[j] < T
13
12
T is not in A
/| T lies beyond A„-
// When n = 12, is the first probe always at A[6] and the second, either at A[3] or
/| A[9]?
//
// In general:
// Is this algorithm sure to terminate?
// How many iterations of the loop could there be?
// Is this algorithm correct? If T is in A is the algorithm guaranteed to find it?
// If T is not in A, must p eventually become larger than q?
Suppose the sublist we’re searching is from A[p] up to A[q] of length k and we
probe unsuccessfully at A[j]:
// k = q – p+1.
A[p]...Alj – 1]
A[] Alj+1]...A[q] -
kl
k2
If A[j] > T, then we will search from A[p] up to Alj – 1] of length kl = j – p.
If A[j] < T, then we will search from A[j + 1] up to A[q] of length k2 = q – j.
We would like kl and k2 to be equal, but if that's not possible (because q – p is
odd), let's consistently make kl the smaller value.
// How should we choose j so that kl <= k2 and k2 is as small as possible?
To make k2 = q – j as small as possible, we need to make j as large as possible.
We want
kl + k2 <= k2+k2,
q - p <= 2(q –j)
2j <= 2q – (q – p) = q+p.
that is,
= 29 – 2j
or
The largest integer j <= (q+p)/2 is [(q + p)/2], and this is the j-value used in the
algorithm.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F0f7775f3-edad-4f27-ba1b-f7886a7505bd%2F6f41df6c-13a0-4250-b344-65d29d1d24c7%2Fjslimv9_processed.png&w=3840&q=75)
Transcribed Image Text:If T = 99, then
A[j]
relation
output
12
16
A[j] < T
9
12
50
A[j] < T
10
11
12
64
A[j] < T
12
12
12
67
A[j] < T
13
12
T is not in A
/| T lies beyond A„-
// When n = 12, is the first probe always at A[6] and the second, either at A[3] or
/| A[9]?
//
// In general:
// Is this algorithm sure to terminate?
// How many iterations of the loop could there be?
// Is this algorithm correct? If T is in A is the algorithm guaranteed to find it?
// If T is not in A, must p eventually become larger than q?
Suppose the sublist we’re searching is from A[p] up to A[q] of length k and we
probe unsuccessfully at A[j]:
// k = q – p+1.
A[p]...Alj – 1]
A[] Alj+1]...A[q] -
kl
k2
If A[j] > T, then we will search from A[p] up to Alj – 1] of length kl = j – p.
If A[j] < T, then we will search from A[j + 1] up to A[q] of length k2 = q – j.
We would like kl and k2 to be equal, but if that's not possible (because q – p is
odd), let's consistently make kl the smaller value.
// How should we choose j so that kl <= k2 and k2 is as small as possible?
To make k2 = q – j as small as possible, we need to make j as large as possible.
We want
kl + k2 <= k2+k2,
q - p <= 2(q –j)
2j <= 2q – (q – p) = q+p.
that is,
= 29 – 2j
or
The largest integer j <= (q+p)/2 is [(q + p)/2], and this is the j-value used in the
algorithm.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education