BinarySearchNR(A[0…n-1], K)
//Input: An array A sorted in ascending order and a search K //Output: An index of the array’s element that is equal to K or -1 if there is no such element
If the key is smaller than the middle element, the key must be in the first half If the key is larger than the middle element, the key must be in the second half
2012-2013-01 《Design and Analysis of Algorithm》 SCUN
2012-12-27 13
Average-Case Analysis (cont.)
• So we can represent binary search as a binary tree:
2012-2013-01 《Design and Analysis of Algorithm》
• Euclid’s algorithm • The kth smallest element find algorithm • Interpolation search
2012-2013-01 《Design and Analysis of Algorithm》 SCUN
2012-12-27 5
What’s the difference? (example)

2012-2013-01 《Design and Analysis of Algorithm》 SCUN
2012-12-27 8
Binary search example：Find the key value 14
0 1 2 3 4 5 6 7 8 9 10 11 12
3 14 27 31 39 42 55 70 74 81 85 93 98
4
3 Types of Decrease and Conquer

Decrease by a constant (usually by 1)
• Insertion sort • Graph traversal algorithms (DFS and BFS) • Algorithms for generating permutations, subsets
2012-2013-01 《Design and Analysis of Algorithm》
SCUN
2012-12-27
3
Decrease-and-Conquer (basic idea)
1.
2. 3.
Reduce problem instance to smaller instance of the same problem Solve smaller instance Extend solution of smaller instance to obtain solution to original instance
k
[ r1 … … … rmid-1 ] rmid [ rmid+1 … … … rn ] （mid=(1+n)/2） k < rmid

k > rmid
First check the middle list element If the key matches the middle element, we are done
Problem of size n
subproblem of size n/2
solution to the subproblem solution to the original problem
2012-2013-01 《Design and Analysis of Algorithm》
SCUN
2012-12-27
2012-2013-01 《Design and Analysis of Algorithm》 SCUN
2012-12-27 12


Average-Case Analysis

Successful Search • If the search is always successful, there are n places (number of possible keys) the key could be found • We will consider each of these to be equivalent and so will give each a probability of 1/n • There is one place we check on the first pass, two places we could check on the second pass, and four places we could check on the third pass, and so on.
Chapter 5
Decrease and Conquer (I)
Introduction to Decrease-and-Conquer Decrease-by-a-Constant-Factor Algorithms The Binary Search Fake-coin Problem Russian Peasant Multiplication Josephus Problem

Combinatorial problem
• • Fake-coin problem (S5.5) Josephus problem (S5.5)
Binary Search (basic idea)

Used with a sorted list (the list is in increasing order)
low=0
27>14
mid=6 55>14 high=5
high=12
mid=2 high=1 mid=0
3<14
low=1 mid=1
14=14
SCUN
2012-12-27 9
2012-2013-01 《Design and Analysis of Algorithm》
The Binary Search Algorithm
Goals of the Lecis lecture, you should
• Master the basic idea and all kinds of variations of decrease and conquer technique • Master the binary search algorithm and its best-case, worstcase and average-case analysis • Understand the fake coin problem and its solution • Be familiar with the Russian peasant multiplication method • Understand the josephus problem and its solution
2012-12-27 6
The Application of Decrease by a constant factor technique

Search problem • The binary search (S4.3, P135-139)

Numerical problem
• Russian peasant multiplication (S5.5)

2012-2013-01 《Design and Analysis of Algorithm》
SCUN
2012-12-27
11
Worst-Case Analysis

In the worst case, we will either find the element on the last pass, or not find the element at all In each pass, only need 1 comparison. Hence, if we knew how many passes it has done, worst case is trivial If n = 2k-1, then there must be k = log(n+1) passes So, informally, we get: Tworst(n) = O(logn) If n is an arbitrary positive integer n, since after one pass, the algorithm faces the same situation but for an array half the size, we get the following recurrence relation for Tworst(n): Tworst(n) = Tworst ( n/2 ) + 1 n>1 Tworst(1) = 1 So, formally: Tworst(n) = logn + 1 = log(n+1) = O(logn)
2012-2013-01 《Design and Analysis of Algorithm》
SCUN
2012-12-27
10
Best-case Analysis
The input instances in which the target matches the middle element will lead to the best case. This means only one comparison is done. So we get: Tbest (n) = Ω(1)