Textbook M.H.Alsuwaiyel,Algorithms design techniques and Analysis,Publishing House of Electronics Industry M.H.Alsuwaiyel著，吴伟昶，方世昌等译，算法设计 技巧与分析，电子工业出版社
Textbook ◼ M. H. Alsuwaiyel, Algorithms design techniques and Analysis, Publishing House of Electronics Industry ◼ M. H. Alsuwaiyel著，吴伟昶，方世昌等译，算法设计 技巧与分析，电子工业出版社
What's Algorithms? An algorithm is a procedure that consists of a finite set of instructions which,given an input from some set of possible inputs,enables us to obtain an output if such an output exists or else obtain nothing at all if there is no output for that particular input through a systematic execution of the instructions
What’s Algorithms? ◼ An algorithm is a procedure that consists of a finite set of instructions which, given an input from some set of possible inputs, enables us to obtain an output if such an output exists or else obtain nothing at all if there is no output for that particular input through a systematic execution of the instructions
Inputs Outputs (Problems) Instructions (Answers) Computers
Instructions Inputs (Problems) Outputs (Answers) Computers
Programming Data Algorithms Software Languages Structure Systems
Programming Languages Data Structure Algorithms Software Systems
Content Chapter 1 Basic Concepts in Algorithmic Analysis Chapter 5 Induction Chapter 6 Divide and Conquer Chapter 7 Dynamic Programming ■ Chapter 8 The Greedy Approach ■ Chapter 9 Graph Traversal Chapter 13 Backtracking Chapter 14 Randomized Algorithms ■ Chapter 15 Approximation Algorithms ■ Chapter 16 Network Flow Chapter 17 Matching
Content ◼ Chapter 1 Basic Concepts in Algorithmic Analysis ◼ Chapter 5 Induction ◼ Chapter 6 Divide and Conquer ◼ Chapter 7 Dynamic Programming ◼ Chapter 8 The Greedy Approach ◼ Chapter 9 Graph Traversal ◼ Chapter 13 Backtracking ◼ Chapter 14 Randomized Algorithms ◼ Chapter 15 Approximation Algorithms ◼ Chapter 16 Network Flow ◼ Chapter 17 Matching
Binary Search Let A[1...n]be a sequence of n elements.Consider the problem of determining whether a given element xis in A
Binary Search ◼ Let A[1…n] be a sequence of n elements. Consider the problem of determining whether a given element x is in A
Binary Search Example: A[1..14]=1457891012152223273235 X=22 Does X exist in A?How many comparisons do you need to give the answer?
Binary Search Example: A[1…14]=1 4 5 7 8 9 10 12 15 22 23 27 32 35 x=22 Does X exist in A? How many comparisons do you need to give the answer?
Binary Search Inputs:(1)An array A[1...n]of n elements sorted in nondecreasing order;(2)x, Output:jif x=A],and 0 otherwise; 1.lowk-1;high-n;衣-0； ■ 2.while (low<high)and (0) ■ 3. midk(low+high)/2; ■ 4. if x=A[mid]then mid; 5. else if x<A[mid]then highmid-1; ■ 6. else low-mid+1; 7.end while; 8.return
Binary Search ◼ Inputs: (1) An array A[1…n] of n elements sorted in nondecreasing order; (2) x; ◼ Output: j if x=A[j], and 0 otherwise; ◼ 1. low1; highn; j0; ◼ 2. while (lowhigh) and (j=0) ◼ 3. mid(low+high)/2; ◼ 4. if x=A[mid] then jmid; ◼ 5. else if x<A[mid] then highmid–1; ◼ 6. else lowmid+1; ◼ 7. end while; ◼ 8. return j;
Binary Search What's the performance of the algorithm Binary Search on a sorted array of size n? What's the minimum number of comparisons we need and in which case it will happen? v What's the maximum number of comparisons we need and in which case it will happen?
Binary Search ◼ What’s the performance of the algorithm Binary Search on a sorted array of size n? ✓ What’s the minimum number of comparisons we need and in which case it will happen? ✓ What’s the maximum number of comparisons we need and in which case it will happen?
Binary Search The number of comparisons performed by the algorithm Binary Search on a sorted array of size n is at most Llog n+1
Binary Search ◼ The number of comparisons performed by the algorithm Binary Search on a sorted array of size n is at most log n+1