{"id":35,"date":"2016-06-18T18:38:00","date_gmt":"2016-06-18T10:38:00","guid":{"rendered":"https:\/\/mille.in\/?p=35"},"modified":"2025-02-21T11:48:58","modified_gmt":"2025-02-21T03:48:58","slug":"%e5%b0%8d%e5%8d%8a%e6%aa%a2%e7%b4%a2%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"https:\/\/mille.in\/?p=35","title":{"rendered":"\u5c0d\u534a\u6aa2\u7d22\u7b97\u6cd5"},"content":{"rendered":"\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>\u6700\u8fd1\u4e00\u500b\u9805\u76ee\uff0c\u7528\u5230\u4e86\u975e\u5e38\u53e4\u8001\u3001\u4e14\u975e\u5e38\u9ad8\u6548\u7684\u5c0d\u534a\u6aa2\u7d22\u7b97\u6cd5\uff0c\u9019\u6b21\u7b2c\u4e8c\u6b21\u4f7f\u7528\u9019\u500b\u7b97\u6cd5\u6a21\u578b\u9032\u884c\u5de5\u7a0b\uff0c\u4e0a\u4e00\u6b21\u662f6\u5e74\u524d<\/p>\n<\/blockquote>\n\n\n\n<h2 class=\"wp-block-heading\">\u95dc\u65bc<\/h2>\n\n\n\n<p>\u5c0d\u534a\u6aa2\u7d22\u7b97\u6cd5\uff0c\u662f\u8907\u96dc\u7684\u96c6\u5408\u5c0d\u8c61\u74b0\u5883\u4e2d\uff0c\u5feb\u901f\u627e\u51fa\u4e00\u500b\u5c0d\u8c61\u7684\u5feb\u901f\u641c\u7d22\u7b97\u6cd5\uff0c\u9069\u7528\u65bc\u5206\u6cbb\u539f\u5247\uff0c\u5c0d\u6578\u64da\u9032\u884c\u6392\u5e8f\u3002<\/p>\n\n\n\n<p>\u5728\u67e5\u627e\u6642\uff0c\u96c6\u5408\u4e2d\u7684\u5c0d\u8c61\u5c07\u6703\u88ab\u5206\u914d\u4e00\u500b\u9375\uff0c\u9375\u7e3d\u6578\u662f2\u7684\u6b21\u65b9\uff0c\u6aa2\u7d22\u6642\uff0c\u6b32\u67e5\u627e\u7684\u5c0d\u8c61\u5c07\u6703\u548c\u96c6\u5408\u4e2d\u7684\u4e2d\u9593\u9ede\u6bd4\u5c0d\uff0c\u5982\u679c\u5927\u65bc\u9375\u503c\uff0c\u90a3\u9ebc\u8a72\u5c0d\u8c61\u5247\u6703\u88ab\u4fdd\u7559\uff0c\u5269\u4e0b\u7684\u6703\u88ab\u62cb\u68c4\uff0c\u76f4\u5230\u96c6\u5408\u4e2d\u53ea\u5269\u4e0b\u4e00\u500b\u5c0d\u8c61\u3002<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"701\" height=\"190\" src=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image.png\" alt=\"\" class=\"wp-image-315\" srcset=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image.png 701w, https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-300x81.png 300w\" sizes=\"auto, (max-width: 701px) 100vw, 701px\" \/><\/figure>\n<\/div>\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:100%\">\n<h2 class=\"wp-block-heading\">\u5de5\u4f5c\u6a21\u5f0f<\/h2>\n<\/div>\n<\/div>\n\n\n\n<p>\u5047\u8a2d\u6211\u5011\u8981\u9069\u7528\u5c0d\u534a\u6aa2\u7d22\u7b97\u6cd5\u627e\u51fa\u5c0d\u8c61<code>31<\/code><\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"544\" height=\"80\" src=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-1.png\" alt=\"\" class=\"wp-image-316\" srcset=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-1.png 544w, https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-1-300x44.png 300w\" sizes=\"auto, (max-width: 544px) 100vw, 544px\" \/><\/figure>\n<\/div>\n\n\n<p>\u9996\u5148\uff0c\u6211\u5011\u9700\u8981\u7528\u9019\u500b\u65b9\u7a0b\u5f0f\u4f86\u627e\u51fa\u4e2d\u9593\u503c<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>mid = low + (high - low) \/ 2<\/code><\/pre>\n\n\n\n<p>0 + (9 &#8211; 0 ) \/ 2 = 4 (integer value of 4.5). \u6240\u4ee5\uff0c\u4e2d\u9593\u503c\u662f<code>4<\/code>.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"544\" height=\"108\" src=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-2.png\" alt=\"\" class=\"wp-image-317\" srcset=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-2.png 544w, https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-2-300x60.png 300w\" sizes=\"auto, (max-width: 544px) 100vw, 544px\" \/><\/figure>\n<\/div>\n\n\n<p>\u6211\u5011\u627e\u51fa\u7684\u6bd4\u8f03\u5b58\u5132\u4f4d<code>4<\/code>\u7684\u503c\u662f<code>27<\/code>,\u4e0d\u5339\u914d\u3002\u56e0\u70ba\u6211\u5011\u8981\u67e5\u627e\u7684\u503c\u5927\u65bc<code>27<\/code>\uff0c\u6240\u4ee5\uff0c\u6211\u5011\u77e5\u9053\u76ee\u6a19\u4e00\u5b9a\u8655\u65bc\u6578\u5217\u7684\u4e0a\u90e8\u3002<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"544\" height=\"80\" src=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-3.png\" alt=\"\" class=\"wp-image-318\" srcset=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-3.png 544w, https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-3-300x44.png 300w\" sizes=\"auto, (max-width: 544px) 100vw, 544px\" \/><\/figure>\n<\/div>\n\n\n<p>\u9032\u884c\u4fee\u6539\uff0c\u5c07<code>low<\/code>&nbsp;\u4fee\u6539\u70ba&nbsp;<code>mid + 1<\/code>\uff0c\u518d\u9032\u884c\u4e2d\u9593\u503c\u67e5\u627e<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>low = mid + 1\nmid = low + (high - low) \/ 2<\/code><\/pre>\n\n\n\n<p>\u73fe\u5728\uff0c\u65b0\u7d50\u679c\u627e\u51fa\u7684\u4e2d\u9593\u503c\u662f<code>7<\/code>\uff0c<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"544\" height=\"122\" src=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-4.png\" alt=\"\" class=\"wp-image-319\" srcset=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-4.png 544w, https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-4-300x67.png 300w\" sizes=\"auto, (max-width: 544px) 100vw, 544px\" \/><\/figure>\n<\/div>\n\n\n<p>\u986f\u7136<code>7<\/code>\u4e0d\u662f\u6211\u5011\u7684\u76ee\u6a19\uff0c\u4f46\u9032\u4e00\u6b65\u7e2e\u5c0f\u7684\u76ee\u6a19\u7bc4\u570d\uff0c\u76ee\u6a19\u61c9\u8a72\u5728\u4e0b\u90e8<\/p>\n\n\n\n<p>\u6240\u4ee5\uff0c\u518d\u6b21\u8a08\u7b97\u4e2d\u9593\u503c\uff0c\u9019\u6b21\u662f<code>5<\/code><\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"544\" height=\"122\" src=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-5.png\" alt=\"\" class=\"wp-image-320\" srcset=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-5.png 544w, https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-5-300x67.png 300w\" sizes=\"auto, (max-width: 544px) 100vw, 544px\" \/><\/figure>\n<\/div>\n\n\n<p>\u547d\u4e2d\uff01\u7d50\u8ad6\u662f\u76ee\u6a19\u503c\u5b58\u5132\u5728\u96c6\u5408\u4e2d<code>5<\/code>\u9019\u500b\u4f4d\u7f6e\u3002<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"544\" height=\"80\" src=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-6.png\" alt=\"\" class=\"wp-image-321\" srcset=\"https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-6.png 544w, https:\/\/mille.in\/wp-content\/uploads\/2016\/06\/image-6-300x44.png 300w\" sizes=\"auto, (max-width: 544px) 100vw, 544px\" \/><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\">\u7bc4\u4f8b<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>Procedure binary_search\n   A \u2190 sorted array\n   n \u2190 size of array\n   x \u2190 value ot be searched\n\n   Set lowerBound = 1\n   Set upperBound = n \n\n   while x not found\n\n      if upperBound &lt; lowerBound \n         EXIT: x does not exists.\n\n      set midPoint = lowerBound + ( upperBound - lowerBound ) \/ 2\n\n      if A&#91;midPoint] &lt; x\n         set lowerBound = midPoint + 1\n\n      if A&#91;midPoint] > x\n         set upperBound = midPoint - 1 \n\n      if A&#91;midPoint] = x \n         EXIT: x found at location midPoint\n\n   end while\n\nend procedure<\/code><\/pre>\n\n\n\n<p><strong>C\u4e0b\u7684\u5be6\u73fe<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>#include &lt;stdio.h>\n\n#define MAX 20\n\n\/\/ array of items on which linear search will be conducted. \nint intArray&#91;MAX] = {1,2,3,4,6,7,9,11,12,14,15,16,17,19,33,34,43,45,55,66};\n\nvoid printline(int count){\n   int i;\n\n   for(i = 0;i &lt;count-1;i++){\n      printf(\"=\");\n   }\n\n   printf(\"=\\n\");\n}\n\nint find(int data){\n   int lowerBound = 0;\n   int upperBound = MAX -1;\n   int midPoint = -1;\n   int comparisons = 0;      \n   int index = -1;\n\n   while(lowerBound &lt;= upperBound){\n      printf(\"Comparison %d\\n\" , (comparisons +1) ) ;\n      printf(\"lowerBound : %d, intArray&#91;%d] = %d\\n\", \n        lowerBound,lowerBound,intArray&#91;lowerBound]);\n      printf(\"upperBound : %d, intArray&#91;%d] = %d\\n\", upperBound,upperBound,intArray&#91;upperBound]);\n      comparisons++;\n\n      \/\/ compute the mid point \n      \/\/ midPoint = (lowerBound + upperBound) \/ 2;\n      midPoint = lowerBound + (upperBound - lowerBound) \/ 2;    \n\n      \/\/ data found\n      if(intArray&#91;midPoint] == data){\n         index = midPoint;\n         break;\n      }else {\n         \/\/ if data is larger \n         if(intArray&#91;midPoint] &lt; data){\n            \/\/ data is in upper half\n            lowerBound = midPoint + 1;\n         }\n         \/\/ data is smaller \n         else{           \n            \/\/ data is in lower half \n            upperBound = midPoint -1;\n         }\n      }               \n   }\n   printf(\"Total comparisons made: %d\" , comparisons);\n   return index;\n}\n\nvoid display(){\n   int i;\n   printf(\"&#91;\");\n\n   \/\/ navigate through all items \n   for(i = 0;i&lt;MAX;i++){\n      printf(\"%d \",intArray&#91;i]);\n   }\n\n   printf(\"]\\n\");\n}\n\nmain(){\n   printf(\"Input Array: \");\n   display();\n   printline(50);\n\n   \/\/find location of 1\n   int location = find(55);\n\n   \/\/ if element was found \n   if(location != -1)\n      printf(\"\\nElement found at location: %d\" ,(location+1));\n   else\n      printf(\"\\nElement not found.\");\n}<\/code><\/pre>\n\n\n\n<p><strong>\u8f38\u51fa\u7d50\u679c<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>Input Array: &#91;1 2 3 4 6 7 9 11 12 14 15 16 17 19 33 34 43 45 55 66 ]\n==================================================\nComparison 1\nlowerBound : 0, intArray&#91;0] = 1\nupperBound : 19, intArray&#91;19] = 66\nComparison 2\nlowerBound : 10, intArray&#91;10] = 15\nupperBound : 19, intArray&#91;19] = 66\nComparison 3\nlowerBound : 15, intArray&#91;15] = 34\nupperBound : 19, intArray&#91;19] = 66\nComparison 4\nlowerBound : 18, intArray&#91;18] = 55\nupperBound : 19, intArray&#91;19] = 66\nTotal comparisons made: 4\nElement found at location: 19<\/code><\/pre>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>\u672c\u6587\u7c21\u8b6f\u81ea<a href=\"http:\/\/www.tutorialspoint.com\/data_structures_algorithms\/binary_search_algorithm.htm\">Tutorialspoint\u7684\u4e00\u7bc7\u6587\u7ae0<\/a><\/p>\n<\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>\u6700\u8fd1\u4e00\u500b\u9805\u76ee\uff0c\u7528\u5230\u4e86\u975e\u5e38\u53e4\u8001\u3001\u4e14\u975e\u5e38\u9ad8\u6548&hellip;<\/p>\n","protected":false},"author":1,"featured_media":324,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[8],"tags":[62],"class_list":["post-35","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-code","tag-62"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/mille.in\/index.php?rest_route=\/wp\/v2\/posts\/35","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mille.in\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mille.in\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mille.in\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mille.in\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=35"}],"version-history":[{"count":3,"href":"https:\/\/mille.in\/index.php?rest_route=\/wp\/v2\/posts\/35\/revisions"}],"predecessor-version":[{"id":322,"href":"https:\/\/mille.in\/index.php?rest_route=\/wp\/v2\/posts\/35\/revisions\/322"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/mille.in\/index.php?rest_route=\/wp\/v2\/media\/324"}],"wp:attachment":[{"href":"https:\/\/mille.in\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=35"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mille.in\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=35"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mille.in\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=35"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}