Basic Algorithm (I)

This section is on sorting and binary, sorting on quicksort and merge, and binary on integer and floating point.

The sorting

Fast row

quick_sort(int q[], int l, int r)

Q is the array to be sorted, L is the left bound of the interval to be sorted, and r is the right bound

  • The basic idea

    1. Take a base value x

      We can take the left boundary value q[l], or the right boundary value q[r], or the middle position value q[L + r >> 1]

    2. : STAR: According to the reference value, adjust the interval so that all values between the left half are ≤x and all values between the right half are ≥x

      The left pointer I starts from the left boundary L and scans to the right; the right pointer J starts from the right boundary R and scans to the left.

      When q[I] < x is satisfied, I shifts to the right; I stops until the condition is not satisfied; Start moving j

      When q[J] > x is satisfied, j shifts to the left. J stops until the condition is not satisfied; Exchange of q[I] and Q [J];

      We move I one to the right, j one to the left.

      Repeat until I and j meet. All the numbers in the left half interval are equal to or less than x, and the last number in the left half interval is equal to or more than x, and the first number in the right half interval is equal to or less than x. The relation between I and j is: I = j + 1 or I = j

    3. I’m going to recurse to the left and right

      Recursive operation [L, j], [j + 1, r] interval, or [L, i-1], [I, r] interval can be

  • Algorithm subject

    Acwing-785 quicksort

    #include<iostream>
using namespace std;
const int N = 100010;
int n;
int q[N];

void quick_sort(int q[], int l, int r) {
    if(l >= r) return; // recursive exit condition, do not write l == r, may occur l > r, can try the case [1,2]
    int x = q[l + r >> 1], i = l - 1, j = r + 1; // set I to l - 1 and j to r + 1 because we update I, j with do while loop,
    while(i < j) { // Do not write I <= j
        do i++; while(q[i] < x);// do not write as <= x, that may be out of bounds to write I, consider [1,1,1].
        // Because the reference value x is a number in the array, when I moves from left to right, it must encounter the number x. If the less than condition is not satisfied, I must stop, thus ensuring that I does not cross the boundary.
        do j--; while(q[j] > x);// cannot be written as >= x, because j may be out of bounds, for the same reason as above
        if(i < j) swap(q[i], q[j]); // If I and j do not meet, then swap 2 numbers
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}

int main(a) {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    quick_sort(q, 0, n - 1);
    for(int i = 0; i < n; i++) printf("%d ", q[i]);
}
Copy the code

  • Pay attention to the point

    When the interval division is over, there are only two conditions for the relative positions of the left pointer I and the right pointer J

    • i = j + 1
    • i = jAt this time,iandjRefers to an element that is exactly equal to the reference valuex)

    If j is used as the boundary of the interval, then [l, j] are ≤x, and [j + 1, r] are ≥x

    If I is used as the boundary of the interval, then [l, I – 1] is ≤x, and [I, r] is ≥x

    When I is used as the boundary, the reference value x cannot reach the left boundary q[l], otherwise an infinite loop will occur, as in use cases [1,2]. At this time, the reference value can be q[r], or Q [L + R + 1 >> 1]. Note that when taking the number in the middle position, 1 should be added to avoid the result of L + R >> 1

    When j is used as the boundary, the reference value x cannot reach the right boundary Q [r], otherwise an infinite loop will occur. The reference value can be q[L] or Q [L + R >> 1].

  • Algorithm template

    // Select one of the following templates for memory: the base value is in the middle position, and the recursive use of j as the boundary
void quick_sort(int q[], int l, int r) {
    if(l >= r) return;
    int x = q[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j) {
        do i++; while(q[i] < x);
        do j--; while(q[j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j);
    quick_sort(q, j + 1, r);
}
Copy the code

  • Thinking summary

    1. Choose a valuex
    2. With this value as the cut-off point, the array is divided into the left and right parts, and the left all partsX or lessAll on the rightX or higher
    3. Perform recursive operations on the left and right parts
Derivative problem: Find the KTH number

Exercise: ACwing-786 the KTH number

#include<iostream>
using namespace std;

const int N = 1e5 +10;
int n, k;
int q[N];

// select the KTH smallest number of array q in [l, r]
int quick_select(int q[], int l, int r, int k) {
    if(l == r) return q[l]; // Find the answer
    int x = q[l + r >> 1], i = l - 1, j = r + 1;
    while(i < j) {
        while(q[++i] < x);
        while(q[--j] > x);
        if(i < j) swap(q[i], q[j]);
    }
    int left = j - l + 1;
    if(k <= left) return quick_select(q, l, j, k);
    else return quick_select(q, j + 1, r, k - left);
}

int main(a) {
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    
    printf("%d", quick_select(q, 0, n - 1, k));
    return 0;
}
Copy the code

merge

merge_sort(int q[], int l, int r)

  • The basic idea

    1. Determine the cut-off point, usually in the middle

    2. Cut the array in half from the cut-off point and sort the left and right parts recursively

    3. :star: Merge the left and right parts of the interval into a single interval (merge 2 ordered arrays into 1 ordered array, using a double pointer)

  • Algorithm subject

    Acwing-787 merge sort

    #include<iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N], tmp[N];

void merge_sort(int q[], int l, int r) {
    if(l >= r) return;
    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);
    / / merge
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r) {
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else tmp[k++] = q[j++];
    }
    while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    for(i = l, j = 0; i <= r; i++, j++) q[i] = tmp[j];
}

int main(a) {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    merge_sort(q, 0, n - 1);
    for(int i = 0; i < n; i++) printf("%d ", q[i]);
}
Copy the code
Derivative title: the number of inversions

Practice: ACwing-788: Number of inversions

#include<iostream>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10;
int n;
int q[N], tmp[N];

// Return the number of inversions in the interval [l, r]
LL merge_sort(int q[], int l, int r) {
    if(l >= r) return 0;
    int mid = l + r >> 1;
    LL cnt = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r); // Calculate the number of inversions in the left and right ranges
    // When merging, calculate the inversions of the numbers in the left and right ranges
    int i = l, j = mid + 1, k = 0;
    while(i <= mid && j <= r) {
        if(q[i] <= q[j]) tmp[k++] = q[i++];
        else {
            cnt += mid - i + 1; tmp[k++] = q[j++]; }}while(i <= mid) tmp[k++] = q[i++];
    while(j <= r) tmp[k++] = q[j++];
    for(int i = l, k = 0; i <= r; i++, k++) q[i] = tmp[k];
    return cnt;
}

int main(a) {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);
    LL cnt = merge_sort(q, 0, n - 1);
    printf("%lld", cnt);
    return 0;
}
Copy the code

binary

Integer binary

  • Algorithm template

    int binary_search_1(int l, int r) {
    while(l < r) {
        int mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

int binary_search_2(int l, int r) {
    while(l < r) {
        int mid = l + r + 1 >> 1;  // If l = mid, add 1 to mid; otherwise, there will be boundary problems
        if(check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}
Copy the code

  • Nature of dichotomy

    Note: the essence of dichotomy is not monotonicity. Monotonicity can be understood as function monotonicity, such as when an array is arranged in ascending or descending order, binary can be used to find the position of a certain number.

    Have monotone sex can dichotomy certainly, but without monotone sex, also can dichotomy possibly.

    The essence of dichotomy is the boundary. Suppose that given an interval, the interval can be divided into left and right parts according to some condition, such that the left side satisfies this condition and the right side does not satisfy this condition (or vice versa). Now you can use dichotomy to find the boundary points of the left and right parts.

    Note that the boundaries of the left and right halves are not the same point, but two adjacent points, because they are integer bisection (discrete). The two algorithms above correspond to finding the boundary of the left half (the right-most point of the red region in the figure above) and the boundary of the right half (the left-most point of the green region in the figure above).

    For example, if we want to find the boundary point of the red part on the left in the figure above, we take mid = L + R >> 1 to determine whether q[mid] satisfies the condition X. If so, it indicates that mid is located in the red region. Our answer is on the right side of mid (mid can be obtained), that is, [mid, r]. L = mid; If q[mid] does not satisfy the condition x, it indicates that mid is located in the green area on the right, and our answer is to the left of mid (mid cannot be obtained), that is, [L, mid-1], then update r = mid-1.

    Note that mid = l + r + 1 >> 1 when mid = l + r + 1 >> 1 when mid = l + r + 1 >> 1 Otherwise, if 1 is not added in mid calculation when L = r-1, mid = L + r >> 1 = L, so update L = mid, that is, L = L, which will lead to an infinite loop. Mid = l + r + 1 >> 1

    Similarly, when r = mid and L = mid + 1 are used, 1 cannot be added when mid is calculated. When L = r-1, if 1 is added when mid is calculated, then mid = L + R + 1 >> 1 = r, so r = mid is updated. It’s r equals r, which leads to an endless loop.

    The simple thing to remember is that only when you update your mid with l = mid, you increment your mid by 1.

Practice: ACwing-789: Range of numbers

#include<iostream>
using namespace std;
const int N = 100010;
int arr[N];
int n,q;

int main(a) {
    scanf("%d%d", &n, &q);
    for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
    
    while(q--) {
        int k;
        scanf("%d", &k);
        
        int l = 0, r = n - 1;
        while(l < r) {
            int mid = l + r >> 1;
            if(arr[mid] >= k) r = mid;
            else l = mid + 1;
        }
        if(arr[l] ! = k)printf("-1 -1\n");
        else {
            printf("%d ", l);
            l = 0, r = n - 1;
            while(l < r) {
                int mid = l + r + 1 >> 1;
                if(arr[mid] <= k) l = mid;
                else r = mid - 1;
            }
            printf("%d\n", l); }}}Copy the code

Floating point dichotomy

Compared with integer dichotomy, floating point dichotomy is simpler without considering the boundary problem.

When the interval of dichotomy is small enough, the answer can be considered to have been found, such as when r-L < 1e-6, stop dichotomy.

Or simply iterate a certain number of times, such as 100 times and then stop dividing.

Exercise: ACwing-790: The third root of a number

#include<iostream>
using namespace std;
int main(a) {
    double n;
    scanf("%lf", &n);
    double l = - 10000., r = 10000;
    
    while(r - l > 1e-8) {
        double mid = (l + r) / 2;
        if(mid * mid * mid >= n) r = mid;
        else l = mid;
    }
    printf("%.6f", l);
}
Copy the code