---
###### tags: `Algorithm`
---
Examples: Divide-and-Conquer Code
===
## Binary Search
### Steps
If x equals the middle item, quit. Otherwise,
1. Divide the array into two subarrays about half as large. If x < middle item, choose the left subarray, otherwise, the right.
2. Conquer the subarray by determining whether x is in that subarray. Unless the subarray is sufficiently small, use recursion to do this.
3. Obtain the solution to the array from the solution to the subarray.
In binary search, the instance is broken down into only one smaller instance. (Combination is NOT required.)
### Code
**Problem:**
Determine whether x is in the sorted array S of n keys.
**Inputs:**
positive integer n, sorted (nondecreasing order) array of keys S indexed from 1 to n, a key x.
**Outputs:**
location, the location of x in S (0 if x is not in S).
:::info
==**Binary Search (Recursive)**==
```pseudo!=
index location (index low, index high){
index mid;
if(low > high)
return 0;
else{
mid = ⌊(low + high)/2⌋;
if(x == S[mid])
return mid;
else if(x < S[mid])
return location(low, mid - 1);
else
return location(mid + 1, high)
}
}
```
:::
:::info
==**Binary Search (Iterative)**==
```pseudo!=
void binsearch(int n, const keytype S[], keytype x, index& location)
{
index low, high, mid;
low = 1; high = n;
location = 0;
while(low <= high && location == 0){
mid = ⌊(low + high)/2⌋;
if(x == S[mid])
location = mid;
else if(x < S[mid])
high = mid - 1;
else
low = mid + 1;
}
}
```
:::
## Mergesort
### Steps
* Divide the array into two subarrays each with n/2 items.
* Conquer each subarray by sorting it. Unless the array is sufficiently small, use recursion to do this.
* Combine the solutions to the subarrays by merging them into a single sorted array.
### Code
* Mergesort
**Problem:** Sort n keys in nondecreasing sequence.
**Inputs:** positive integer n, array of keys S indexed from 1 to n.
**Outputs:** the array S containing the keys in nondecreasing order.
:::info
==**Mergesort (Recursive)**==
```pseudo!=
void mergesort(int n, keytype S[]){
if(n > 1){
const int h = ⌊n/2⌋, m = n - h;
keytype U[1...h], V[1...m];
copy S[1] through S[h] to U[1] through U[h];
copy S[h + 1] through S[n] to V[1] through V[m];
mergesort(h, U);
mergesort(m, V);
merge(h, m, U, V, S);
}
}
```
==**Merge**==
**Problem:** Merge two sorted arrays into one sorted array.
**Inputs:** positive integers h and m, array of sorted keys U indexed from 1 to h, array of sorted keys V indexed from 1 to m.
**Outputs:** an array S indexed from 1 to h + m containing the keys in U and V in a single sorted array.
```pseudo!=
void merge (int h, int m, const keytype U[],
const keytype V[],
keytype S[])
{
index i, j, k;
i = 1; j = 1; k = 1;
while(i <= h && j <= m){
if(U[i] < V[j]){
S[k] = U[i];
i++;
}
else{
S[k] = V[j];
j++;
}
k++;
}
if(i > k)
copy V[j] through V[m] to S[k] through S[h + m];
else
copy U[i] through U[h] to S[k] through S[h + m];
}
```
:::
:::info
==**Mergesort2 (Recursive)**==
```pseudo!=
void mergesort2(index low, index high){
index mid;
if(low < high){
mid = ⌊(low + high)/2⌋;
mergesort2(low, mid);
mergesort2(mid + 1, high);
merge2(low, mid, high);
}
}
```
==**Merge2**==
**Problem:** Merge the two sorted subarrays of S created in Mergesort 2.
**Inputs:** indices low, mid, and high, and the subarray of S indexed from low to high. The keys in array slots from low to mid are already sorted in nondecreasing order, as are the keys in array slots from mid + 1 to high.
**Outputs:** the subarray of S indexed from low to high containing the keys in nondecreasing order.
```pseudo!=
void merge2 (index low, index mid, index high)
{
index i, j, k;
keytype U[low...high];
// A local array needed for the merging
i = low; j = mid + 1; k = low;
while(i <= mid && j <= high){
if(S[i] < S[j]){
U[k] = S[i];
i++;
}
else{
U[k] = S[j];
j++;
}
k++;
}
if(i > mid)
move S[j] through S[high] to U[k] through U[high];
else
move S[i] through S[mid] to U[k] through U[high];
move U[low] through U[high] to S[low] through S[high];
}
```
:::
:::info
==**Mergesort (Iterative)**==
```java!=
// Iteratively sort subarray `A[low…high]` using a temporary array
public static void mergesort(int[] A)
{
int low = 0;
int high = A.length - 1;
// sort array `A[]` using a temporary array `temp`
int[] temp = Arrays.copyOf(A, A.length);
// divide the array into blocks of size `m`
// m = [1, 2, 4, 8, 16…]
for (int m = 1; m <= high - low; m = 2*m)
{
// for m = 1, i = 0, 2, 4, 6, 8 …
// for m = 2, i = 0, 4, 8, 12 …
// for m = 4, i = 0, 8, 16 …
// …
for (int i = low; i < high; i += 2*m)
{
int from = i;
int mid = i + m - 1;
int to = Integer.min(i + 2*m - 1, high);
merge(A, temp, from, mid, to);
}
}
}
```
==**Merge**==
```java!=
// Merge two sorted subarrays `A[from…mid]` and `A[mid+1…to]`
public static void merge(int[] A, int[] temp, int from, int mid, int to)
{
int k = from, i = from, j = mid + 1;
// loop till no elements are left in the left and right runs
while (i <= mid && j <= to)
{
if (A[i] < A[j]) {
temp[k++] = A[i++];
}
else {
temp[k++] = A[j++];
}
}
// copy remaining elements
while (i < A.length && i <= mid) {
temp[k++] = A[i++];
}
/* no need to copy the second half (since the remaining items
are already in their correct position in the temporary array) */
// copy back to the original array to reflect sorted order
for (i = from; i <= to; i++) {
A[i] = temp[i];
}
}
```
:::
## Quicksort
### Steps
* Pivot
* to be used to partition the array by Pivot (items smaller than pivot, items larger than pivot)
* it can be any item, and for convenience we use the first item in the input array.
* The partition procedure is continued until an array with one item is reached.
- Worst Case：Ο(n2)
當資料的順序恰好為由大到小或由小到大時
有分割跟沒分割一樣
* **j:** Pivot 要換的位置 或是 比 Pivot。
* **i:** 指正在檢查的位置。
* 在下一次顯示交換結果。
### Code
:::info
==**Quicksort (Recursive)**==
**Problem:** Sort n keys in nondecreasing order.
**Inputs:** positive integer n, array of keys S indexed from 1 to n.
**Outputs:** the array S containing the keys in nondecreasing order.
```pseudo!=
void quicksort(index low, index high){
index pivotpoint;
if(high > low){
partition(low, high, pivotpoint);
quicksort(low, pivotpoint - 1);
quicksort(pivotpoint + 1, high);
}
}
```
==**Partition**==
**Problem:** Partition the array S for Quicksort.
**Inputs:** two indices, low and high, and the subarray of S indexed from low to high.
**Outputs:** pivotpoint, the pivot point for the subarray indexed from low to high.
```pseudo!=
void partition(index low, index high, index& pivotpoint)
{
index i, j;
keytype pivotitem;
pivotitem = S[low]; // Choose first item for pivotitem.
j = low;
for(i = low + 1; i <= high; i++){
if(S[i] < pivotitem){
j++;
exchange S[i] and S[j];
}
}
pivotpoint = j;
exchange S[low] and S[pivotpoint]; //Put pivotitem at pivotpoint
}
```
:::
## Strassen’s Matrix Multiplication
### Steps
* Suppose we want the product C of two 2 × 2 matrices, A and B. That is,
$$
\left\lbrack \matrix{c_{11} & c_{12} \cr c_{21} & c_{22}} \right\rbrack =
\left\lbrack \matrix{a_{11} & a_{12} \cr a_{21} & a_{22}} \right\rbrack \times \left\lbrack \matrix{b_{11} & b_{12} \cr b_{21} & b_{22}} \right\rbrack
$$
* Strassen determined that if we let (這是推出來的，要背起來)
$$
\begin{split}
m_1 &= (a_{11} + a_{22})(b_{11} + b_{22}) \\
m_2 &= (a_{21} + a_{22})b_{11} \\
m_3 &= a_{11}(b_{12} - b_{22}) \\
m_4 &= a_{22}(b_{21} - b_{11}) \\
m_5 &= (a_{11} + a_{12})b_{22} \\
m_6 &= (a_{21} - a_{11})(b_{11} + b_{12}) \\
m_7 &= (a_{12} - a_{22})(b_{21} + b_{22})
\end{split}
$$
* the product C is given by
$$
C = \left\lbrack \matrix{m_1 + m_4 - m_5 + m_7 & & m_3 + m_5 \cr m_2 + m_4 & & m_1 + m_3 - m_2 + m_6} \right\rbrack
$$
### Code
:::info
==**Strassen**==
**Problem:** Determine the product of two n × n matrices where n is a power of 2.
**Inputs:** an integer n that is a power of 2, and two n × n matrices A and B.
**Outputs:** the product C of A and B.
```pseudo!=
void strassen(int n
n * n_matrix A,
n * n_matrix B,
n * n_matrix& C){
if(n <= threshold)
compute C = A * B using the standard algorithm (n^3);
else{
partition A into four submatrices A11, A12, A21, A22;
partition B into four submatrices B11, B12, B21, B22;
compute C = A * B using Strassen's method;
// example recursive call: strassen(n/2, A11 + A22, B11 + B22, M1);
}
}
```
:::
Sign in with Wallet
Connect another wallet