{"id":76,"date":"2010-06-30T21:34:34","date_gmt":"2010-06-30T13:34:34","guid":{"rendered":"http:\/\/comzyh.gicp.net\/myblog\/?p=76"},"modified":"2013-01-05T13:19:02","modified_gmt":"2013-01-05T05:19:02","slug":"%e4%ba%8c%e5%88%86%e6%9f%a5%e6%89%be","status":"publish","type":"post","link":"https:\/\/comzyh.com\/blog\/archives\/76\/","title":{"rendered":"\u4e8c\u5206\u67e5\u627e"},"content":{"rendered":"<p>\u6240\u8c13\u4e8c\u5206\u67e5\u627e,\u5c31\u662f\u5728<strong>\u6709\u5e8f<\/strong>\u7684\u6570\u7ec4\u4e2d\u67e5\u627e\u67d0\u4e00\u503c\u7684\u5143\u7d20,\u57fa\u672c\u65b9\u6cd5\u662f\u5206\u6cbb<\/p>\n<h2>\u4e0d\u4fdd\u8bc1Key(\u6240\u67e5\u627e\u7684\u5173\u952e\u5b57)\u5728\u96c6\u5408\u4e2d\u7684\u67e5\u627e<\/h2>\n<p>\u4f8b\u5982\uff1a\u6700\u957f\u4e0d\u4e0b\u964d\u5b50\u5e8f\u5217\u4e2d\u7684\u4e8c\u5206\u67e5\u627e,\u5f53\u52a8\u89c4\u5230\u67d0\u4e00\u4f4d\u7f6e\u65f6,\u8981\u77e5\u9053\u5728\u8f85\u52a9\u6570\u7ec4\u4e2dKey\u7684\u4f4d\u7f6e,\u9700\u8981\u627e\u5230Key\u6240\u5728\u4f4d\u7f6e\u6216\u4ec5\u6bd4Key\u5c0f\u7684\uff08\\(\\)c[i]\\leqslant key<c[i+1][\/latex] i\u662f\u4e8c\u5206\u7684\u8fd4\u56de\u503c\uff09\n2013-1-5 \u8865\u5145\u4e2a\u66f4\u7b80\u5355\u7684\n\n\n<pre lang=\"CPP\">\r\ninline int bin(int x)\r\n{\r\n\tint b=0,e=MAX,k=(b+e+1)>>1;\r\n\twhile (b<e)\r\n\t{\r\n\t\tif (f[k]>x)e=k-1;\r\n\t\telse\r\n\t\t\tif (f[k]<=x)b=k;\r\n\t\tk=(b+e+1)>>1;\r\n\t}\r\n\treturn k;\r\n}\r\n\/\/\u5173\u952e\u5728\u4e8e&#8221;k=(b+e+1)>>1;&#8221;\r\n\/\/\u8fd9\u6761\u8bed\u53e5\u80fd\u6ee1\u8db3\u4e00\u4e2a\u5f88\u597d\u7684\u6027\u8d28,\u5373b,e\u5982\u679c\u76f8\u90bb\u7684\u8bdd(e-b=1),\u5219k=e\u800c\u4e0d\u662fb,\u5f53\u7136,\u5982\u679ce-b=2\u7684\u65f6\u5019,k=(b+e)\/2\r\n<\/pre>\n<p>CODE:<\/p>\n<pre lang='C'>\r\n#include <stdio.h>\r\n int bins(int key) {\r\n    static int l,r,y;\/\/l:\u5de6\u754c,r,\u53f3\u754c\r\n    l=0;r=n;\r\n    while (l<=r){\r\n          y=(l+r)>>1;\/\/\u4f4d\u8fd0\u7b97\u53f3\u79fb,\u76f8\u5f53\u4e8e\u96642\r\n          if (m[y] > key) r=y-1;else\r\n          if (m[y] < key) {if (m[y+1]>key) return y;else l=y+1;}\/\/\u8fd9\u91cc\u5927\u62ec\u53f7\u4e3a\u4e86\u9605\u8bfb\u65b9\u4fbf\r\n          else return y;\r\n          }\r\n    }\r\n<\/pre>\n<p>\u8fd9\u6837\u5199\u597d\u50cf\u5f88\u7b80\u5355<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u6240\u8c13\u4e8c\u5206\u67e5\u627e,\u5c31\u662f\u5728\u6709\u5e8f\u7684\u6570\u7ec4\u4e2d\u67e5\u627e\u67d0\u4e00\u503c\u7684\u5143\u7d20,\u57fa\u672c\u65b9\u6cd5\u662f\u5206\u6cbb \u4e0d\u4fdd\u8bc1Key(\u6240\u67e5\u627e\u7684\u5173\u952e\u5b57)\u5728\u96c6\u5408\u4e2d\u7684\u67e5\u627e [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[9,30],"tags":[21],"class_list":["post-76","post","type-post","status-publish","format-standard","hentry","category-9","category-non-solution","tag-21"],"jetpack_publicize_connections":[],"aioseo_notices":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p6XQWE-1e","jetpack-related-posts":[],"jetpack_likes_enabled":true,"_links":{"self":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/76","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/comments?post=76"}],"version-history":[{"count":3,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/76\/revisions"}],"predecessor-version":[{"id":759,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/posts\/76\/revisions\/759"}],"wp:attachment":[{"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/media?parent=76"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/categories?post=76"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/comzyh.com\/blog\/wp-json\/wp\/v2\/tags?post=76"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}