ASTU
CSE 1101 Introduction to Computing
Lecture 17
Divide and conquer
Binary search, Merge sort
Department of Computer Science and Engi-
neering
The School of EE & Computing
Adama Science & Technology University
OUTLINE ASTU
Divide and conquer
Binary search
Merge sort
2
DIVIDE AND CONQUER ASTU
“Divide and conquer” is a strategy to solve a
problem.
Given a (hard) problem, it divides the problem into
sub-problems, and solves the sub-problems in-
dependently, and finally combines their solu-
tions to obtain a solution of the original problem.
3
ASTU
Julius Caesar(BC 100 - 44): “divide and impera”
(or divide and rule) to govern the European conti-
nent.
The British practiced this idea to control the Indian
sub-continent(1858 - 1947).
Benjamin Franklin(1706 - 1790): “We must all
hang together, or assuredly we shall all hang
separately.”
4
ASTU
Sequential Search
L = [(“John”, 20), (“Mary”, 19), (“David”, 22), (“-
James”, 21),
(“Young”, 19), (“Susan”,22)]
Given the name of a person and an unsorted list,
report his/her age.
5
ASTU
def seq_search(L, qname):
for i in range(len(L)):
name, age = L[i]
if qname == name: How many comparisons?
return age At most n comparisons,
return -1 where n = len(L) !
seq_search(L, “David”)
6
ASTU
What if L is sorted?
Try “Jeff.” You may stop after comparing it with
“John”.
Why?
= [(John, 20), (Mary),
L = [(David, 22), (James, 21), (John, 20), (Mary, 19),
(Susan,22)], (Young, 19)]
However, we need n comparisons in the worst case,
anyway, where n = len(L). Why?
7
BINARY SEARCH ASTU
Basic idea
Assumption: the list L is sorted.
L = [1, 2, 6, 8, 11, 17, 23]
q = 19
low = 0 3 high= 6
1 2 6 8 11 17
23
mid = (low + high) / 2
L[mid] = 8
With a single comparison, we can reduce the search
space by half. Divide and conquer!
8
ASTU
How many comparisons? 2 + 1 = 3
0 3 6
19 > L[mid] 1 2 6 8 11 17
8 23
4 5 6
19 > L[mid] 1 2 6 8 11 17
17 23
6
19 == L[mid] 1 2 6 8 11 17
23 23
(low = high = mid)
9
ASTU
Observations
1. When low == high, one additional compari-
son is required to make the final decision. At this
time, the length of the sub-list is reduced to one.
base case
2. As long as high > low, the length of the sub-
list
reduced by half with a single comparison.
recursive case
10
ASTU
With a single comparison, the search space is
reduced by half. In order to make the final deci-
sion, the search space should be reduced to one.
How many comparisons are required to make the fi-
nal decision ? At most Why?
n/ = 1 k = , where n = len(L).
+1
to make the final decision
to reduce the search space
11
ASTU
def b_search(L, q, low, high):
if low == high:
return L[low] == q Base case
mid = (low + high) / 2
if L[mid] == q: Recursive case
return True
elif L[mid] < q:
return b_search(L, q, mid+1, high) Why this ?
else: Try L =[5, 7] and q =
if low != mid: 3!
return b_search(L, q, low, mid-1)
else:
return False 12
MERGE SORT ASTU
Basic Idea
1. If the list is of length 0 or 1, it is already sorted.
the base case
2. Otherwise, divide the list into two sub-lists of
(almost) equal size and sort each of them recur-
sively by using merge sort .
the recursive case
3. Merge the results.
Divide and conquer
13
ASTU
[23, 2, 8, 6, 17, 11, 20, 7]
[23, 2, 8, 6] [17, 11, 20, 7]
divide
[23, 2] [8, 6] [17, 11] [20, 7]
[23] [2] [8] [6] [17] [11] [20] [7]
[2, 23] [6, 8] [11, 17] [7, 20]
[2, 6, 8, 23] [7, 11, 17, 20] merge
[2, 6, 7, 8, 11, 17, 20, 23]
14
ASTU
def merge_sort(L):
if len(L) < 2:
base case
return L[:]
mid = len(L) / 2
left = merge_sort(L[:mid ]) recursive case
right = merge_sort(L[mid:])
return merge(left, right)
L =[23, 2, 8, 6, 17, 11, 20, 7]
L = merge_sort(L)
print L
15
ASTU
How to merge to sorted lists
output left
[2, 6, 8, 23]
[2, 6]
[7, 11, 17, 20]
right
How many comparisons?
len(left) + len(right) – 1 = n - 1, where n =
len(L).
Why?
At most n comparisons.
16
ASTU
def merge(left, right):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
[Link](left[i])
i += 1
else:
[Link](right[j])
j += 1
while i < len(left):
[Link](left[i])
i += 1
No more elements in right
while j < len(right):
[Link](right[j])
j += 1 No more elements in left
return result
17
ASTU
def merge_sort(L):
if len(L) < 2:
return L[:]
mid = len(L) / 2
left = merge_sort(L[:mid])
right = merge_sort(L[mid:])How many comparisons?
return merge(left, right)
L =[23, 2, 8, 6, 17, 11, 20, 7]
L = merge_sort(L)
print L
18
ASTU
1 [23, 2, 8, 6, 17, 11, 20, 7]
2 [23, 2, 8, 6] [17, 11, 20, 7]
divide
3 [23, 2] [8, 6] [17, 11] [20, 7]
[23] [2] [8] [6] [17] [11] [20] [7]
1 [2, 23] [6, 8] [11, 17] [7, 20]
2 [2, 6, 8, 23] [7, 11, 17, 20] merge
3 [2, 6, 7, 8, 11, 17, 20, 23]
How many rounds ?
How many comparisons per round?
19
ASTU
How many rounds?
n/ =1
=n k=
How many comparisons at each round?
At most n comparisons
Therefore, at most n comparisons
O(n )
20
ASTU
Behavior of the merge sort.
The dividing and merging phases are mixed un-
like the figure in the previous slide !
21
ASTU
def merge_sort(L): [23, 2, 6, 8, 17, 11, 20, 7]
global lv [23, 2, 8, 6]
lv += 1 [2, 23]
if len(L) < 2: [23]
display(L) [2]
lv -= 1 [2, 23]
return L[:] [8 6]
display(L) [8]
mid = len(L) / 2 [6]
left = merge_sort(L[:mid]) [6, 8]
right = merge_sort(L[mid:]) [2, 6, 8, 23]
result = merge(left, right) [17, 11, 20, 7]
display(result) [17, 11]
[17]
lv -= 1
[11]
return result
lv = -1 [11, 17]
def display(L): L= [20, 7]
if lv == 0: [23,2,6,8,17,11,20,7 [20]
] [7]
print L
[7, 20]
else: merge_sort(L)
[7, 11, 17, 20]
print " " * 4 * lv, L 22
[2, 6, 7, 8, 11, 17, 20, 23]
