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