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. 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 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 1pq<rm, 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