西安电子科技大学：《数据结构与算法分析 Data Structure and Algorithm Analysis》课程教学资源（PPT课件讲稿）06 Algorithm Analysis and Sorting

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 Instructions (Problems) (Answers) Computers

Instructions Inputs (Problems) Outputs (Answers) Computers

Programming Data Software Algorithms Languages Structure Systems

Programming Languages Data Structure Algorithms Software Systems

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. low1; highn; j0; ◼ 2. while (lowhigh) and (j=0) ◼ 3. mid(low+high)/2; ◼ 4. if x=A[mid] then jmid; ◼ 5. else if x<A[mid] then highmid–1; ◼ 6. else lowmid+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 Algorithm BINARYSEARCH on a sorted array of size n is at most Llog n+1

Binary Search ◼ The number of comparisons performed by Algorithm BINARYSEARCH on a sorted array of size n is at most log n+1

Binary Search Can you implement the Binary Search in a certain kind of computer language?

Binary Search ◼ Can you implement the Binary Search in a certain kind of computer language?

Merging Two Sorted Lists Suppose we have an array A[1...m]and three indices p,g,and r,with 1sp<g<r<m,such that both the subarrays A[p...g]and Ag+1...]are individually sorted in nondecreasing order.We want to rearrange the elements in A so that the elements in the subarray A[p...]are sorted in nondecreasing order

Merging Two Sorted Lists ◼ Suppose we have an array A[1…m] and three indices p, q, and r, with 1pq<rm, such that both the subarrays A[p…q] and A[q+1…r] are individually sorted in nondecreasing order. We want to rearrange the elements in A so that the elements in the subarray A[p…r] are sorted in nondecreasing order