{"id":1228,"date":"2024-07-29T18:30:00","date_gmt":"2024-07-29T10:30:00","guid":{"rendered":"https:\/\/diary.bid\/?p=1228"},"modified":"2025-08-30T18:32:34","modified_gmt":"2025-08-30T10:32:34","slug":"%e7%ac%ac%e4%b8%80%e7%ab%a0-%e5%9f%ba%e7%a1%80%e7%ae%97%e6%b3%95%ef%bc%88%e4%b8%80%ef%bc%89","status":"publish","type":"post","link":"https:\/\/diary.bid\/?p=1228","title":{"rendered":"\u7b2c\u4e00\u7ae0 \u57fa\u7840\u7b97\u6cd5\uff08\u4e00\uff09"},"content":{"rendered":"\n
\n

\u672c\u8282\u5185\u5bb9\u4e3a\u90e8\u5206\u6392\u5e8f\u548c\u67e5\u627e\u7b97\u6cd5\uff0c\u6570\u636e\u7ed3\u6784\u8bfe\u8bb2\u8fc7\uff0c\u4e0d\u8fc7\u5f53\u65f6\u671f\u672b\u65f6\u95f4\u7d27\uff0c\u6ca1\u53bb\u542c\u8bfe\uff0c\u867d\u7136PPT\u770b\u61c2\u4e86\uff0c\u4f46\u662f\u4ece\u6ca1\u6709\u81ea\u5df1\u5b8c\u6574\u6572\u8fc7\uff0c\u73b0\u5728\u539f\u7406\u4e5f\u90fd\u5fd8\u4e86\uff0c\u5b66\u4e00\u904d\u53d1\u73b0\u786e\u5b9e\u6709\u4e9b\u5730\u65b9\u5bb9\u6613\u5199\u9519\u3002<\/p>\n<\/blockquote>\n\n\n\n

\u5feb\u901f\u6392\u5e8f<\/h2>\n\n\n\n

\u6838\u5fc3\u601d\u8def<\/h3>\n\n\n\n

\u4e3b\u8981\u601d\u60f3\uff1a\u5206\u6cbb<\/p>\n\n\n\n

    \n
  1. \u786e\u5b9a\u5206\u754c\u70b9\uff1aq[l]<\/code>\u6216\u8005q[(l+r)\/2]<\/code>\u6216\u8005q[r]<\/code>\uff1b<\/li>\n\n\n\n
  2. \u8c03\u6574\u8303\u56f4\uff1a\u76ee\u6807\u662f\u5de6\u8fb9\u7684\u6570\u90fd\u5c0f\u4e8e\u7b49\u4e8ex\uff0c\u53f3\u8fb9\u7684\u6570\u90fd\u5927\u4e8e\u7b49\u4e8ex\uff08\u5206\u754c\u70b9\u4e0d\u4e00\u5b9a\u662fx\uff09\uff1b<\/li>\n\n\n\n
  3. \u9012\u5f52\u5904\u7406\u5de6\u53f3\u4e24\u7aef<\/li>\n<\/ol>\n\n\n\n

    \u7b2c2\u6b65\u5b9e\u73b0<\/h3>\n\n\n\n

    \u66b4\u529b\u7b97\u6cd5<\/h4>\n\n\n\n
      \n
    1. \u5f00\u4e24\u4e2a\u6570\u7ec4a[ ]\u548cb[ ]\uff1b<\/li>\n\n\n\n
    2. \u628aq[ ]\u4e2d\u4ecel\u5230r\u904d\u5386\uff1a<\/li>\n<\/ol>\n\n\n\n
        \n
      • q[i]<=x \u653e\u5165a;<\/li>\n\n\n\n
      • q[i]>x \u653e\u5165b;<\/li>\n<\/ul>\n\n\n\n
          \n
        1. \u628aa[ ]\u548cb[ ]\u653e\u5165q[ ]\u4e2d<\/li>\n<\/ol>\n\n\n\n

          \u5e38\u7528\u601d\u8def<\/h4>\n\n\n\n
            \n
          1. \u8bbe\u5b9a\u4e24\u4e2a\u6307\u9488\uff0c\u4ece\u5de6\u53f3\u4e24\u7aef\u5f00\u59cb\uff1a<\/li>\n<\/ol>\n\n\n\n
              \n
            • \u5de6\u6307\u9488\u4ece\u5de6\u5411\u53f3\u5bfb\u627e\u7b2c\u4e00\u4e2a\u5927\u4e8e\u7b49\u4e8e\u57fa\u51c6\u7684\u5143\u7d20<\/li>\n\n\n\n
            • \u53f3\u6307\u9488\u4ece\u53f3\u5411\u5de6\u5bfb\u627e\u7b2c\u4e00\u4e2a\u5c0f\u4e8e\u7b49\u4e8e\u57fa\u51c6\u7684\u5143\u7d20<\/li>\n<\/ul>\n\n\n\n
                \n
              1. \u627e\u5230\u4e4b\u540e\u4ea4\u6362\u4e24\u4e2a\u5143\u7d20<\/li>\n\n\n\n
              2. \u6301\u7eed\u79fb\u52a8\u5de6\u53f3\u6307\u9488\u5e76\u4ea4\u6362\u5143\u7d20\uff0c\u76f4\u5230\u4e24\u4e2a\u6307\u9488\u76f8\u9047\uff0c\u6b64\u65f6\u7ed3\u675f<\/li>\n<\/ol>\n\n\n\n

                \u4ee3\u7801<\/h3>\n\n\n\n

                \u81ea\u5df1\u624b\u5199\u4e86\u4e00\u904d\uff1a<\/p>\n\n\n\n

                void quicksort(int a[], int l, int r){\n    if(l>=r) return;\n    int cha = a[l];\n    int x = l+1, y = r;\n    while(x<=y){\n        while(x<=y){\n            if(a[x]>cha) break;\n            x++;\n        }\n        while(x<=y){\n            if(a[y]<cha) break;\n            y--;\n        }\n        if(x<y){\n            swap(a[x],a[y]);\n        }\n    }\n    swap(a[l],a[y]);\n    if(l<y)quicksort(a,l,y-1);\n    if(y+1<r)quicksort(a,y+1,r);\n}<\/code><\/pre>\n\n\n\n
                \u8001\u5e08\u7ed9\u7684\u4ee3\u7801\uff1a<\/p>\n\n\n\n
                void quicksort(int q[], int l, int r){\n    if(l>=r) return;\n    int x = q[l], i = l - 1, j = r + 1; \/\/\u6b64\u5904-1\u548c+1\u90fd\u662f\u4e3a\u4e86\u540e\u9762do while\u7b80\u6d01\n    while(i < j){\n        do i++; while (q[i] < x);\n        do j--; while (q[j] > x);\n        if(i<j) swap(q[i],q[j]);\n    }\n    quicksort(q,l,j);\/\/\u53d6j\u65f6\u524d\u9762\u4e0d\u80fd\u662fx = q[r]\n    quicksort(q,j+1,r);\n    \/\/quicksort(q,l,i-1); \u53d6i\u65f6\u524d\u9762\u4e0d\u80fd\u662fx = q[l]\n    \/\/quicksort(q,i,r);\n}<\/code><\/pre>\n\n\n\n
                STL\u7684\u5feb\u901f\u6392\u5e8f\u51fd\u6570<\/h3>\n\n\n\n
                #include <algorithm>\nstd::sort(arr, arr + n);<\/code><\/pre>\n\n\n\n
                \u9ed8\u8ba4\u4ece\u5c0f\u5230\u5927\uff0c\u8303\u56f4\u4e3a\u6570\u7ec4arr<\/code>\u5230arr+n-1<\/code><\/p>\n\n\n\n
                \u91cd\u6784\uff1a<\/strong>\u6307\u5b9acmp<\/code>\u6392\u5e8f\u51fd\u6570\uff08\u4ee5\u7ed3\u6784\u4f53\u4e3a\u4f8b\uff09\uff1a<\/p>\n\n\n\n
                #include <iostream>\n#include <algorithm>\nusing namespace std;\n\nstruct Person {\n    string name;\n    int age;\n};\n\nbool cmp(const Person& a, const Person& b) {\n    return a.age < b.age; \/\/ \u6309\u5e74\u9f84\u5347\u5e8f\n}\n\/\/\u8fd9\u91cc\u4f7f\u7528(const Person& a, const Person& b)\u662f\u56e0\u4e3a\u8282\u7701\u7a7a\u95f4\uff0c\u4f7f \u7528\u5f15\u7528\u7c7b\u578b\uff0c\u907f\u514d\u518d\u590d\u5236\u4e00\u4efd\u53d8\u91cf\uff0c\u4f7f\u7528const\u662f\u9632\u6b62\u51fd\u6570\u4fee\u6539\u539f\u6765\u7684\u503c\uff0cconst\u662f\u4fdd\u62a4\u63aa\u65bd\u3002\n\nint main() {\n    Person arr[] = { {"Alice", 30}, {"Bob", 25}, {"Charlie", 35} };\n    int n = sizeof(arr) \/ sizeof(arr[0]);\n\n    sort(arr, arr + n, cmp);\n\n    for (int i = 0; i < n; i++) \n        cout << arr[i].name << " " << arr[i].age << endl;\n    \/\/ \u8f93\u51fa\uff1a\n    \/\/ Bob 25\n    \/\/ Alice 30\n    \/\/ Charlie 35\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n
                \u5f52\u5e76\u6392\u5e8f<\/h2>\n\n\n\n
                \u4e3b\u8981\u601d\u8def<\/h3>\n\n\n\n
                \u4e3b\u8981\u601d\u60f3\uff1a\u5206\u6cbb<\/p>\n\n\n\n
                  \n
                1. \u786e\u5b9a\u5206\u754c\u70b9: $mid = \\frac{l + r}{2}$<\/li>\n\n\n\n
                2. \u9012\u5f52\u6392\u5e8f\u5de6\u8fb9\u548c\u53f3\u8fb9<\/li>\n\n\n\n
                3. \u5408\u5e76\u4e24\u4e2a\u6570\u7ec4\u4e3a\u4e00\u4e2a\u6570\u7ec4\uff08\u5f52\u5e76\uff09<\/li>\n<\/ol>\n\n\n\n
                  \u4ee3\u7801<\/h3>\n\n\n\n
                  int linshi[100000];\nvoid binggui(int a[], int l, int r){\n    if(l>=r) return;\n    int mid = (l+r)\/2;\n    binggui(a,l,mid);\n    binggui(a,mid+1,r);\n    int i = l, j = mid + 1;\n    int now = l;\n    while(i<=mid&&j<=r){\n        if(a[i]>a[j]) linshi[now++] = a[j++];\n        else linshi[now++] = a[i++];\n    }\n    while(i<=mid) linshi[now++] = a[i++];\n    while(j<=r) linshi[now++] = a[j++];\n    for(int t = l; t <= r; t++) a[t] = linshi[t];\n}<\/code><\/pre>\n\n\n\n
                  \u6574\u6570\u4e8c\u5206<\/h2>\n\n\n\n
                  \u6709\u5355\u8c03\u6027\u4e00\u5b9a\u53ef\u4ee5\u4e8c\u5206\uff0c\u6ca1\u6709\u5355\u8c03\u6027\u4e5f\u6709\u53ef\u80fd\u4e8c\u5206\u3002<\/p>\n\n\n\n
                  \"image-20250728195714059\"\/<\/figure>\n\n\n\n
                  \u6b65\u9aa4<\/h3>\n\n\n\n
                    \n
                  1. \u9009\u53d6\u4e00\u4e2a\u70b9 $mid = \\frac{l + r + 1}{2}$ \uff08$+1$ \u662f\u4e3a\u4e86\u4e0a\u53d6\u6574\uff0c\u4e3a\u4e86\u4e0b\u9762 $True$ \u65f6\u4e0d\u4f1a\u51fa\u73b0\u533a\u95f4\u53d8\u6210 $[mid,r] = [l,r]$ \u800c\u4ea7\u751f\u5faa\u73af\uff09<\/li>\n\n\n\n
                  2. $if(check(mid))$ \uff08\u68c0\u67e5\u662f\u5426\u5c5e\u4e8e\u5de6\u534a\u8fb9\uff0c\u6bd4\u5982\u68c0\u67e5 $mid \\le cha$ \uff09<\/li>\n<\/ol>\n\n\n\n
                      \n
                    • $Ture$ -> \u6539\u53d8 $l=mid$<\/li>\n\n\n\n
                    • $False$ -> \u6539\u53d8 $r = mid - 1$<\/li>\n<\/ul>\n\n\n\n
                      \u6b64\u65f6\u53d6\u5f97\u7684\u662f\u7b49\u503c\u7684\u6700\u540e\u4e00\u4e2a<\/p>\n\n\n\n
                      \u6216\u8005<\/strong><\/p>\n\n\n\n
                        \n
                      1. \u9009\u53d6 $mid = \\frac{l+r}{2}$ \uff08\u6b64\u5904\u540c\u7406\uff0c\u9ed8\u8ba4\u4e0b\u53d6\u6574\uff0c\u4e3a\u4e86\u4e0d\u4f1a\u4ea7\u751f $[l,r]$\uff09<\/li>\n\n\n\n
                      2. $if(check(mid))$ \uff08\u68c0\u67e5\u662f\u5426\u5c5e\u4e8e\u53f3\u534a\u8fb9\uff0c\u6bd4\u5982\u68c0\u67e5 $mid \\ge cha$ \uff09<\/li>\n<\/ol>\n\n\n\n
                          \n
                        • $True$ -> \u6539\u53d8 $r = mid$<\/li>\n\n\n\n
                        • $False$ -> \u6539\u53d8 $l = mid + 1$<\/li>\n<\/ul>\n\n\n\n
                          \u6b64\u65f6\u53d6\u5f97\u7684\u662f\u7b49\u503c\u7684\u7b2c\u4e00\u4e2a<\/p>\n\n\n\n
                          \u4ee3\u7801<\/h3>\n\n\n\n
                          int bsearch(int a[], int l, int r){\n    while(l < r){\n        int mid = l + r >> 1;\n        if (check(mid)) r = mid;\n        else l = mid + 1;\n    }\n    return l;\n}\n\nint bsearch(int a[], int l, int r){\n    while(l < r){\n        int mid = l + r + 1 >> 1;\n        if (check(mid)) l = mid;\n        else r = mid - 1;\n    }\n    return l;\n}<\/code><\/pre>\n\n\n\n
                          \u81ea\u5e26bsearch\u51fd\u6570<\/h3>\n\n\n\n
                          \u5fc5\u987b\u8981\u5148\u5f15\u5165cstdlib<\/code>\u5e93\u3002<\/p>\n\n\n\n
                          \u5b9a\u4e49<\/h4>\n\n\n\n
                          void* bsearch(\n    const void* key,     \/\/ \u4f60\u8981\u627e\u7684\u4e1c\u897f\u7684\u5730\u5740\n    const void* base,    \/\/ \u6392\u597d\u5e8f\u7684\u6570\u7ec4\u7684\u9996\u5730\u5740\n    size_t nmemb,        \/\/ \u6570\u7ec4\u91cc\u6709\u51e0\u4e2a\u5143\u7d20\n    size_t size,         \/\/ \u6bcf\u4e2a\u5143\u7d20\u591a\u5927\uff08\u4ee5\u5b57\u8282\u4e3a\u5355\u4f4d\uff09\n    int (*compar)(const void*, const void*)  \/\/ \u6bd4\u8f83\u51fd\u6570\u7684\u5730\u5740\n);<\/code><\/pre>\n\n\n\n
                          \u4e3e\u4f8b<\/h4>\n\n\n\n
                          #include <iostream>\n#include <cstdlib>  \/\/ bsearch\u5728\u8fd9\u91cc\u9762\n\n\/\/ \u6bd4\u8f83\u51fd\u6570\nint compare(const void* a, const void* b) {\n    int va = *(const int*)a;\n    int vb = *(const int*)b;\n    if (va < vb) return -1;\n    else if (va > vb) return 1;\n    else return 0;\n}\n\nint main() {\n    int arr[] = {1, 3, 5, 7, 9};  \/\/ \u6709\u5e8f\u6570\u7ec4\n    int n = sizeof(arr) \/ sizeof(arr[0]);\n    int key = 5;\n\n    \/\/ \u7528 bsearch \u67e5\u627e key\n    int* found = (int*) bsearch(&key, arr, n, sizeof(int), compare);\n\n    if (found != nullptr) {\n        std::cout << "\u627e\u5230\u4e86\uff0c\u503c\u662f: " << *found << std::endl;\n    } else {\n        std::cout << "\u6ca1\u627e\u5230" << std::endl;\n    }\n\n    return 0;\n}<\/code><\/pre>\n\n\n\n
                          \u6d6e\u70b9\u6570\u4e8c\u5206<\/h2>\n\n\n\n
                          \u6ca1\u6709\u6574\u9664\u7684\u8003\u8651\uff0c\u6240\u4ee5\u7b80\u4fbf\u4e00\u4e9b\u3002<\/p>\n\n\n\n
                          \u4e3e\u4f8b\uff1a\u67e5\u627e\u67d0\u4e2a\u6570\u7684\u5f00\u6839\u503c\u3002<\/p>\n\n\n\n
                          #include <iostream>\n\nusing namespace std;\n\nint main(){\n    double x;\n    cin >> x;\n\n    double l = 0, r = x;\n    while(r- l> 1e-8){\n        double mid = (l + r)\/2;\n        if(mid*mid>=x) r = mid;\n        else l = mid;\n    }\n    printf("%lf\\n",l);\n    return 0;\n}<\/code><\/pre>\n
                          <\/g><\/svg>\u6765\u81ea\u5317\u4eac<\/div>","protected":false},"excerpt":{"rendered":"
                          \u672c\u8282\u5185\u5bb9\u4e3a\u90e8\u5206\u6392\u5e8f\u548c\u67e5\u627e\u7b97\u6cd5\uff0c\u6570\u636e\u7ed3\u6784\u8bfe\u8bb2\u8fc7\uff0c\u4e0d\u8fc7\u5f53\u65f6\u671f\u672b\u65f6\u95f4\u7d27\uff0c\u6ca1\u53bb\u542c\u8bfe\uff0c\u867d\u7136PPT\u770b\u61c2\u4e86\uff0c\u4f46\u662f\u4ece\u6ca1\u6709\u81ea\u5df1\u5b8c […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2,104],"tags":[105],"class_list":["post-1228","post","type-post","status-publish","format-standard","hentry","category-study","category-biji","tag-105"],"_links":{"self":[{"href":"https:\/\/diary.bid\/index.php?rest_route=\/wp\/v2\/posts\/1228","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/diary.bid\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/diary.bid\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/diary.bid\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/diary.bid\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1228"}],"version-history":[{"count":1,"href":"https:\/\/diary.bid\/index.php?rest_route=\/wp\/v2\/posts\/1228\/revisions"}],"predecessor-version":[{"id":1229,"href":"https:\/\/diary.bid\/index.php?rest_route=\/wp\/v2\/posts\/1228\/revisions\/1229"}],"wp:attachment":[{"href":"https:\/\/diary.bid\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1228"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/diary.bid\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1228"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/diary.bid\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1228"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}