COMP 250
INTRODUCTION TO COMPUTER SCIENCE
Week 9-3 : Recursion 2 (Binary Search)
Giulia Alberini, Fall 2020
WHAT ARE WE GOING TO DO IN THIS VIDEO?
More recursive algorithms
Decimal to Binary conversion Power function
Binary Search
RECALL: DECIMAL TO BINARY (ITERATIVE)
ALGORITHM Constructing Base 2 Expansions
procedure BinaryExpansion(𝑛) 𝑘≔0
While 𝑛 > 0
𝑎𝑘 ≔ 𝑛%2 n≔ 𝑛/2 𝑘≔𝑘+1
return (𝑎𝑘−1, … , 𝑎1, 𝑎0)
Recall that a decimal number 𝑛 requires approximately log2 𝑛 bits for its binary representation.
DECIMAL TO BINARY (RECURSIVE)
ALGORITHM Constructing Base 2 Expansions
procedure BinaryExpansion(𝑛) If 𝑛 > 0:
BinaryExpansion(𝑛/2) print(𝑛%2)
Also in this case, there are log2 𝑛 recursive calls
POWER (𝑥𝑛) – DEFINITION Definition of power
Inductive definition: Base clause:
Inductive clause:
𝑥𝑛 =𝑥⋅𝑥⋯𝑥
𝑛 times
𝑥0 = 1
𝑥𝑛 =𝑥⋅𝑥𝑛−1
POWER (𝑥𝑛) – ITERATIVE 1
Let 𝑥 a positive integer and let 𝑛 be a positive number.
power(x, n) {
int result =1;
for(int i=1; i<=n; i++) {
result = result *x;
}
return result;
}
POWER (𝑥𝑛) – RECURSIVE
power(x, n) {
if(n==0) {
return 1;
} else {
return x*power(x,n-1);
}
}
POWER() – CAN WE DO BETTER?
More interesting approach using recursion:
𝑥18 = 𝑥9∗𝑥9
𝑥9 = 𝑥4∗𝑥4∗𝑥
𝑥4 = 𝑥2∗𝑥2 𝑥2 = 𝑥∗𝑥
POWER (𝑥𝑛) – RECURSIVE 2
power( x, n) {
if (n == 0)
return 1; else if (n == 1)
return x;
else{
tmp = power(x, n/2);
if (n%2==0)
return tmp*tmp;
else
// one multiplication
return tmp*tmp*x; // two multiplications }
}
A SIMILAR IDEA CAN BE IMPLEMENTED ITERATIVELY
IDEA: Let’s use the binary expansion of 𝑛, say 𝑛 = 𝑎𝑘−1, ... , 𝑎1, 𝑎0 2. Note that:
𝑥𝑛 = 𝑥𝑎𝑘−12𝑘−1+⋯+𝑎12+𝑎0 = 𝑥𝑎𝑘−12𝑘−1 ⋯ 𝑥𝑎12 ⋅ 𝑥𝑎0
This shows how to compute 𝑥𝑛: we only need to compute the values
of 𝑥, 𝑥2, 𝑥2 2 = 𝑥4,...,𝑥2𝑘. Once we have these terms we multiply the
terms𝑥2𝑗,where𝑎 =1. 𝑗
POWER (𝑥𝑛) – ITERATIVE 2
power(x, n) { result = 1; pow = x; if(n%2 == 1)
result = x;
n = n/2;
while(n != 0) {
pow = pow * pow; if(n%2 == 1)
Let𝑛= 𝑎𝑘−1,...,𝑎1,𝑎0 2
// log2(𝑛)−1 iterations // 1 multiplication
result = result * pow; // 1 multiplication n = n/2;
}
return result;
}
POWER (𝑥𝑛) – ITERATIVE 2
power(x, n) { result = 1; pow = x; if(n%2 == 1)
result = x; n = n/2;
while(n != 0) {
pow = pow * pow; if(n%2 == 1)
Let 𝑛 = 𝒂𝒌−𝟏,...,𝒂𝟏,𝒂𝟎 2
// log2(𝑛)−1 iterations // 1 multiplication
result = result * pow; // 1 multiplication n = n/2;
}
return result;
}
POWER (𝑥𝑛) – ITERATIVE 2
power(x, n) { result = 1; pow = x; if(n%2 == 1)
result = x;
n = n/2;
while(n != 0) {
pow = pow * pow; if(n%2 == 1)
Let 𝑛 = 𝒂𝒌−𝟏,...,𝒂𝟏,𝑎0 2
// log2(𝑛)−1 iterations // 1 multiplication
result = result * pow; // 1 multiplication n = n/2;
}
return result;
}
EXAMPLE: 𝑥243
𝑛 = (243)10 = (11110011)2
Q: How many multiplications do we need?
EXAMPLE: 𝑥243
𝑛 = (243)10 = (11110011)2
Q: How many multiplications do we need?
A: Recursive method: 5*2 + 2*1 = 12. Iterative method: 7 + 5 = 12
The highest order bit in the recursive method is the base case, and doesn’t require a multiplication.
The lowest order bit in the iterative method does not require multiplication.
EXAMPLE: 𝑥243
𝑛 = (243)10 = (11110011)2
Q: How many multiplications do we need? A: 𝑂(log𝑛)
OBSERVATIONS
The second approach we looked at uses fewer multiplications than the first one, and thus the second approach seems faster.
Q: Is this indeed the case? A: No. Why not ?
OBSERVATIONS
Hint: Let 𝑥 be a positive integer with M digits.
𝑥2 has about ? digits. 𝑥3 has about ? digits. :
𝑥𝑛 has about ? digits.
OBSERVATIONS
Hint: Let 𝑥 be a positive integer with M digits.
𝑥2 has about 2M digits. 𝑥3 has about 3M digits. :
𝑥𝑛 has about 𝑛 ∗ M digits.
We cannot assume that multiplication takes ‘constant’ time.
Taking large powers gives very large numbers and multiplications becomes more expensive.
BINARY SEARCH
SEARCHING A LIST
Goal: find a given element in a list.
Solution: go through all the elements in the list and check whether
the element is there (linear search).
Could we do this any faster if the list was sorted to begin with?
Think of how you search for a term in an index. Do you start at the beginning and then scan through to the end? (No.)
BINARY SEARCH
Inputs:
A sorted list.
The element we are looking for (the key)
IDEA: First compare the key with the element in the middle of the list
If the key is less than the middle element, we only need to search the first half of the list, so we continue searching on this smaller list.
If the key is greater than the middle element, we only need to search the second half of the list, so we continue searching on this smaller list.
If the key equals the middle element, we have a match – return its index. http://www.oxfordmathcenter.com/drupal7/node/31
EXAMPLE
Search for 25
1
5
31
35
-4
6
14
23
52
70
EXAMPLE
Search for 25
Look at the middle element and compare
1
5
31
35
-4
6
14
23
52
70
EXAMPLE
Search for 25
Look at the middle element and compare
If not equal: discard half of the list and keep searching on the other half
31
35
-4 1 5 6 14
23
52
70
EXAMPLE
Search for 25
Look at the middle element and compare
31
35
-4 1 5 6 14
23
52
70
EXAMPLE
Search for 25
Look at the middle element and compare
If not equal: discard half of the list and keep searching on the other half
-4 1 5 6 14
23
31
35 52 70
EXAMPLE
Search for 25
Look at the middle element and compare
-4 1 5 6 14
23
31
35 52 70
EXAMPLE
Search for 25
Look at the middle element and compare
If not equal: discard half of the list and keep searching on the other half
-4 1 5 6 14 23
31
35 52 70
EXAMPLE
Search for 25
Look at the middle element and compare
-4 1 5 6 14 23
31
35 52 70
EXAMPLE
Search for 25
Look at the middle element and compare
If not equal: discard half of the list and keep searching on the other half
-4 1 5 6 14 23
31 35 52 70
EXAMPLE
Search for 25
There are no more elements in the listthe element is not there! Return -1.
-4 1 5 6 14 23
31 35 52 70
IMPLEMENT BINARY SEARCH
Idea: keep track of the left and right indices denoting the section of the list that needs to be searched.
What is the index of the element that we compare to the key as a function of the left and right indices?
BACK TO EXAMPLE
Search for 25 (initialize left and right)
1
5
31
35
-4
6
14
23
52
70
left = 0 right = 9 right = size -1
BACK TO EXAMPLE
Search for 25
Look at the middle element and compare (compute mid)
mid = (left+right)/2 mid = 4
1
5
31
35
-4
6
14
23
52
70
left = 0
right = 9
BACK TO EXAMPLE
Search for 25
Look at the middle element and compare
If not equal: discard half of the list and keep searching on the other half (update left)
mid = 4
31
35
-4 1 5 6 14
23
left = 5 right = 9 left = mid +1
52
70
EXAMPLE
Search for 25
Look at the middle element and compare (compute mid)
mid = (left+right)/2 =7
31
35
-4 1 5 6 14
23
52
70
left = 5
right = 9
EXAMPLE
Search for 25
Look at the middle element and compare
If not equal: discard half of the list and keep searching on the other half (update right)
mid = 7
-4 1 5 6 14
23
31
35 52 70
left=5 right=6 = mid -1
EXAMPLE
Search for 25
Look at the middle element and compare (compute mid)
mid = 5
-4 1 5 6 14
23
31
35 52 70
left=5 right=6
EXAMPLE
Search for 25
Look at the middle element and compare
If not equal: discard half of the list and keep searching on the other half (update left)
mid = 5
-4 1 5 6 14 23
31
35 52 70
left = 6 right = 6
EXAMPLE
Search for 25
Look at the middle element and compare (compute mid)
mid = 6
-4 1 5 6 14 23
31
35 52 70
left = 6 right = 6
EXAMPLE
Search for 25
Look at the middle element and compare
If not equal: discard half of the list and keep searching on the other half (update right)
mid = 6
-4 1 5 6 14 23
31 35 52 70
right= 5 left = 6
EXAMPLE
Search for 25
There are no more elements in the list (right