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<<m,such that both the subarrays A[p...]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
Merging Two Sorted Lists Example: A[1..7]=5811481012 p=1,q=3,=7 4[1...3]and A[4...7]are already sorted nondecreasingly, please sort A nondecreasingly?How many comparisons do you need to give the answer?
Merging Two Sorted Lists Example: A[1…7]=5 8 11 4 8 10 12 p=1, q=3, r=7 A[1…3] and A[4…7] are already sorted nondecreasingly, please sort A nondecreasingly? How many comparisons do you need to give the answer?
Merging Two Sorted Lists Inputs:(1)A[1...m];(2)p,g,and r,and 1≤psq<Km,such that both Ap..g]and Ag+1..月 are sorted individually in nondecreasing order; Output:A[p...contains the result of merging the two subarrays A[p...g]and Ag+1...];
Merging Two Sorted Lists ◼ Inputs: (1) A[1…m]; (2) p, q, and r, and 1pq<rm, such that both A[p…q] and A[q+1…r] are sorted individually in nondecreasing order; ◼ Output: A[p…r] contains the result of merging the two subarrays A[p…q] and A[q+1…r];
Merging Two Sorted Lists 1.S-p,tk-q外1；k-P; 2.while sg and tr 3. if A[s]d then 4. 瓦←-ALS]; 5. s-s+1; 6. else ◆ 7. 氏←-AL; 8. t-t+1i 9. end if; ■ 10. k-k+1; ■ 11. end while; 12.ifS=qt1then瓦k.←-At..月 13.else瓦k..←-As.q] ■ 14.end if ■15.ALp.月←-p.月
Merging Two Sorted Lists ◼ 1. sp; tq+1; kp; ◼ 2. while sq and tr ◼ 3. if A[s]A[t] then ◼ 4. B[k]A[s]; ◼ 5. ss+1; ◼ 6. else ◼ 7. B[k]A[t]; ◼ 8. tt+1; ◼ 9. end if; ◼ 10. kk+1; ◼ 11. end while; ◼ 12. if s=q+1 then B[k…r]A[t…r] ◼ 13. else B[k…r]A[s…q] ◼ 14. end if ◼ 15. A[p…r]B[p…r]