2.3-1:
2.3-2:
function MERGE - IMPROVED(A,p,q,r){ create array B[ 0 ... r - p]; int i = p, j = q + 1 , t = 0 ; while (i <= q && j <= r){ if (A[i] >= A[j]){ B[t ++ ] = A[j ++ ]; } else { B[t ++ ] = A[i ++ ]; } } if (i > q){ // i pile exhausted while (j <= r) B[t ++ ] = A[j ++ ]; } else if (j > r){ // j pile exhausted while (i <= q) B[t ++ ] = A[i ++ ]; } // copy the elements back for ( i = 0 ; i <= r - q; i ++ ){ A[p + i] = B[i]; }}
2.3-3:
2.3-4:
// recursive insertion sort R_IS(A,s,e){ // s: start index; e: end index if (e <= s) return ; R_IS(A,s,e - 1 ); // here we use linear search; while it's possible to use binary // then theoretically, it can achieve a worst time O(n lgn) for ( int i = e - 1 ; i >= s; i -- ){ if (A[i] < A[e]) swap(A,i,e); }}
2.3-5:
/* @params: * A: sortted array * s: starting position * e: end position * key: the search key we're looking for * @return: * -1 if not found * one of the index of the key if found */ // binary search recursive B - SEARCH - R( int A[], int s, int e, int key){ if (s > e) return - 1 ; int mid = (s + e) / 2 ; if (A[mid] > key){ return B - SEARCH - R(A,s,mid - 1 ,key); } else if (A[mid] < key){ return B - SEARCH - R(A,mid + 1 ,e,key); } else return mid;} // binary search iterative B - SEARCH - I( int A[], int s, int e, int key){ while (s <= e){ mid = (s + e) / 2 ; if (A[mid] < key){ s = mid + 1 ; } else if (A[mid] > key){ e = mid - 1 ; } else { return mid; } } return mid;} /* Short argue that the run time is O(lg n): * it's a tree has lg n levels, each level has 1 node. */
2.3-6: (updated after the first comment given for this blog post)
We can use a binary search to make it O(n lg n) for search, but cannot improve for moving elements. Therefore, the overall complexity is unchanged.
2.3-7:
(1) merge-sort -- O(n lg n)
(2) for every element, use binary search to check whether it can form a sum with every element comes later.