{"id":74,"date":"2019-05-12T21:55:59","date_gmt":"2019-05-12T13:55:59","guid":{"rendered":"https:\/\/kanghaov.com\/?p=74"},"modified":"2020-06-24T16:22:25","modified_gmt":"2020-06-24T08:22:25","slug":"%ef%bc%9a%e4%ba%8c%e5%88%86%e6%9f%a5%e6%89%be%e5%92%8c%e5%a4%a7o%e8%a1%a8%e7%a4%ba%e6%b3%95","status":"publish","type":"post","link":"https:\/\/nemo.cool\/74.html","title":{"rendered":"\u4e8c\u5206\u67e5\u627e\u548c\u5927O\u8868\u793a\u6cd5"},"content":{"rendered":"<h1>\u672c\u7ae0\u5185\u5bb9<\/h1>\n<ul>\n<li>\u7f16\u5199\u7b2c\u4e00\u79cd\u67e5\u627e\u7b97\u6cd5\uff1a\u4e8c\u5206\u67e5\u627e<\/li>\n<li>\u5b66\u4e60\u5982\u4f55\u8c08\u8bba\u7b97\u6cd5\u7684\u8fd0\u884c\u65f6\u95f4\uff1a\u5927O\u8868\u793a\u6cd5<\/li>\n<li>\u4e86\u89e3\u4e00\u79cd\u5e38\u7528\u7684\u8bbe\u8ba1\u65b9\u6cd5\uff1a\u9012\u5f52<\/li>\n<\/ul>\n<hr \/>\n<h4>\u4ec0\u4e48\u662f\u7b97\u6cd5\uff1f<\/h4>\n<ul>\n<li>\u7b97\u6cd5\u662f\u4e00\u7ec4\u5b8c\u6210\u4efb\u52a1\u7684\u6307\u4ee4\uff0c\u4efb\u4f55\u4ee3\u7801\u7247\u6bb5\u90fd\u53ef\u4ee5\u89c6\u4e3a\u7b97\u6cd5\u3002<\/li>\n<\/ul>\n<hr \/>\n<h3>\u4e8c\u5206\u67e5\u627e<\/h3>\n<ul>\n<li>\u4e8c\u5206\u67e5\u627e\u662f\u4e00\u79cd\u7b97\u6cd5\uff0c\u5176\u8f93\u5165\u662f\u4e00\u4e2a<strong>\u6709\u5e8f<\/strong>\u7684\u5143\u7d20\u5217\u8868(\u4ec5\u5f53\u5217\u8868\u6709\u5e8f\u7684\u65f6\u5019\uff0c\u4e8c\u5206\u67e5\u627e\u624d\u7ba1\u7528)\u3002\u5982\u679c\u8981\u67e5\u627e\u7684\u5143\u7d20\u5305\u542b\u5728\u5217\u8868\u4e2d\uff0c\u4e8c\u5206\u67e5\u627e\u8fd4\u56de\u5176\u4f4d\u7f6e\uff0c\u5426\u5219\u8fd4\u56denull\u3002<\/li>\n<\/ul>\n<h5>\u9996\u5148\u4ecb\u7ecd\u7b80\u5355\u67e5\u627e<\/h5>\n<p>\u7b80\u5355\u67e5\u627e\u5c31\u662f\u2018\u50bb\u627e\u2019\uff0c\u4f8b\u5982\u731c\u6d4b\u4e00\u4e2a1~100\u7684\u6570\u5b57\uff0c\u4ece1\u5f00\u59cb\u4f9d\u6b21\u5f80\u4e0a\u731c\uff0c\u6bcf\u6b21\u731c\u6d4b\u53ea\u80fd\u6392\u9664\u4e00\u4e2a\u6570\u5b57\u3002\u5982\u679c\u6570\u5b57\u662f99\uff0c\u5219\u9700\u8981\u731c\u6d4b99\u6b21\u624d\u80fd\u731c\u5230\u3002<\/p>\n<h6>\u4e8c\u5206\u67e5\u627e<\/h6>\n<ul>\n<li>\u800c\u4e8c\u5206\u67e5\u627e\u6cd5\u5219\u4ece50\u5f00\u59cb\uff0c\u4e00\u4e0b\u5b50\u53ef\u4ee5\u6392\u9664\u4e00\u534a\u7684\u6570\u5b57\uff1b\u6bcf\u6b21\u90fd\u731c\u6d4b\u4e2d\u95f4\u7684\u6570\u5b57\uff0c\u4ece\u800c\u6bcf\u6b21\u90fd\u5c06\u5269\u4f59\u7684\u6570\u5b57\u6392\u9664\u4e00\u534a\u3002<\/p>\n<\/li>\n<li>\n<p>\u4e00\u822c\u800c\u8a00\uff0c\u5bf9\u4e8e\u5305\u542bn\u4e2a\u5143\u7d20\u7684\u5217\u8868\uff0c\u7528\u4e8c\u5206\u67e5\u627e\u6700\u591a\u9700\u8981[latex]\\log n[\/latex]\u6b65\uff0c\u800c\u7b80\u5355\u67e5\u627e\u6700\u591a\u9700\u8981n\u6b65\u3002<\/p>\n<\/li>\n<\/ul>\n<h5>\u4e8c\u5206\u67e5\u627ePython\u4ee3\u7801\u5b9e\u73b0<\/h5>\n<pre><code class=\"\">def binary_search(list, item):\n    low = 0\n    high = len(list) - 1 \n    while low &lt;= high: #\u53ea\u8981\u8303\u56f4\u6ca1\u6709\u7f29\u5c0f\u5230\u53ea\u5305\u542b\u4e00\u4e2a\u5143\u7d20\uff0c\u5c31\u68c0\u67e5\u4e2d\u95f4\u7684\u5143\u7d20\n        mid = (low + high) \/\/ 2\n        guess = list[mid]\n        if guess == item: #\u627e\u5230\u5143\u7d20\u4e86\n            return mid\n        if guess &gt; item: #\u731c\u7684\u503c\u5927\u4e86\n            high = mid - 1\n        else: #\u731c\u7684\u503c\u5c0f\u4e86\n            low = mid + 1\n    return None #\u6ca1\u6709\u731c\u6d4b\u7684\u503c\n\n\nlist = [1, 2, 3, 4, 5, 6, 7]\n\n# \u80fd\u627e\u5230\u5bf9\u5e94\u7684\u503c\nprint(binary_search(list, 3))\nprint(binary_search(list, 6))\n\n# \u4e0d\u80fd\u627e\u5230\u5bf9\u5e94\u7684\u503c\nprint(binary_search(list, 8))\n\n<\/code><\/pre>\n<h2><a href=\"https:\/\/kanghaov.com\/80.html\" title=\"leetcode\u4e2d\u7684\u4e8c\u5206\u67e5\u627e\">leetcode\u4e2d\u7684\u4e8c\u5206\u67e5\u627e<\/a><\/h2>\n<h3>\u8fd0\u884c\u65f6\u95f4<\/h3>\n<ul>\n<li>\u7ebf\u6027\u65f6\u95f4(linear time)\uff1a\u4ee5\u7b80\u5355\u67e5\u627e\u4e3a\u4f8b\uff0c\u6700\u591a\u7684\u731c\u6d4b\u6b21\u6570\u4e0e\u5217\u8868\u957f\u5ea6\u76f8\u540c\uff0c\u8fd9\u88ab\u79f0\u4e3a<strong>\u7ebf\u6027\u65f6\u95f4<\/strong>-O(n)\u3002<\/li>\n<li>\u5bf9\u6570\u65f6\u95f4(log\u65f6\u95f4):\uff1a\u6bd4\u5982\u4e8c\u5206\u67e5\u627e-O(log n).<\/li>\n<\/ul>\n<p><strong>\u7ebf\u6027\u65f6\u95f4\u548c\u5bf9\u6570\u65f6\u95f4\u7684\u589e\u901f\u4e0d\u540c\uff01<\/strong><\/p>\n<h4>\u5927O\u8868\u793a\u6cd5<\/h4>\n<p>\u5927O\u8868\u793a\u6cd5\u662f\u4e00\u79cd\u7279\u6b8a\u7684\u8868\u793a\u6cd5\uff0c\u6307\u51fa\u4e86\u7b97\u6cd5\u7684\u901f\u5ea6\u6709\u591a\u5feb\uff0c<strong>\u540c\u65f6\u4e5f\u8868\u793a\u4e86\u7b97\u6cd5\u7684\u589e\u901f\u7684\u5dee\u5f02<\/strong>\uff0c\u5176\u5355\u4f4d\u5e76\u4e0d\u662f\u79d2\uff0c\u800c\u662f<strong>\u64cd\u4f5c\u6570<\/strong>\uff0c\u6307\u51fa\u4e86<strong>\u6700\u7cdf\u7cd5<\/strong>\u60c5\u51b5\u4e0b\u7684\u8fd0\u884c\u65f6\u95f4\u3002<\/p>\n<h5>\u4e00\u4e9b\u5e38\u89c1\u7684\u5927O\u8fd0\u884c\u65f6\u95f4<\/h5>\n<p>\u4ece\u5feb\u5230\u6162\uff1a<br \/>\nO(log n)    \u5bf9\u6570\u65f6\u95f4\uff0c\u5982\u4e8c\u5206\u67e5\u627e<br \/>\nO(n)    \u7ebf\u6027\u65f6\u95f4\uff0c\u5982\u7b80\u5355\u67e5\u627e<br \/>\nO(n * log n )   \u7ebf\u6027\u5bf9\u6570\u65f6\u95f4\uff0c\u5982\u5feb\u901f\u6392\u5e8f<br \/>\nO([latex]n^{2}[\/latex]) \u5e73\u65b9\u65f6\u95f4\uff0c\u5982\u9009\u62e9\u6392\u5e8f<br \/>\nO(n!)   \u9636\u4e58\u65f6\u95f4\uff0c\u5982\u65c5\u884c\u5546\u95ee\u9898<\/p>\n<h5>\u5c0f\u7ed3<\/h5>\n<ul>\n<li>\u7b97\u6cd5\u7684\u901f\u5ea6\u6307\u7684\u5e76\u975e\u65f6\u95f4\uff0c\u800c\u662f\u64cd\u4f5c\u6570\u7684\u589e\u901f<\/li>\n<li>\u8c08\u8bba\u7b97\u6cd5\u7684\u901f\u5ea6\u65f6\uff0c\u6211\u4eec\u8bf4\u7684\u662f\u968f\u7740\u8f93\u5165\u7684\u589e\u52a0\uff0c\u5176\u8fd0\u884c\u65f6\u95f4\u5c06\u4ee5\u4ec0\u4e48\u6837\u7684\u901f\u5ea6\u589e\u52a0\u3002<\/li>\n<li>\u7b97\u6cd5\u7684\u8fd0\u884c\u65f6\u95f4\u7528\u5927O\u8868\u793a\u6cd5\u8868\u793a<\/li>\n<li>O(log n)\u6bd4O(n)\u5feb\uff0c\u5f53\u9700\u8981\u641c\u7d22\u7684\u5143\u7d20\u8d8a\u591a\u65f6\uff0c\u524d\u8005\u6bd4\u540e\u8005\u5feb\u7684\u8d8a\u591a\u3002<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>\u672c\u7ae0\u5185\u5bb9 \u7f16\u5199\u7b2c\u4e00\u79cd\u67e5\u627e\u7b97\u6cd5\uff1a\u4e8c\u5206\u67e5\u627e \u5b66\u4e60\u5982\u4f55\u8c08\u8bba\u7b97\u6cd5\u7684\u8fd0\u884c\u65f6\u95f4\uff1a\u5927O\u8868\u793a\u6cd5 \u4e86\u89e3\u4e00\u79cd\u5e38\u7528\u7684\u8bbe\u8ba1\u65b9\u6cd5\uff1a\u9012\u5f52 \u4ec0\u4e48\u662f\u7b97\u6cd5\uff1f \u7b97\u6cd5\u662f\u4e00\u7ec4\u5b8c\u6210\u4efb\u52a1\u7684\u6307\u4ee4\uff0c\u4efb\u4f55\u4ee3\u7801\u7247\u6bb5\u90fd\u53ef\u4ee5\u89c6\u4e3a\u7b97\u6cd5\u3002 \u4e8c\u5206\u67e5\u627e \u4e8c\u5206\u67e5\u627e\u662f\u4e00\u79cd\u7b97\u6cd5\uff0c\u5176\u8f93\u5165\u662f\u4e00\u4e2a\u6709\u5e8f\u7684\u5143\u7d20\u5217\u8868(\u4ec5\u5f53\u5217\u8868\u6709\u5e8f\u7684\u65f6\u5019\uff0c\u4e8c\u5206\u67e5\u627e\u624d\u7ba1\u7528)\u3002\u5982\u679c\u8981\u67e5\u627e\u7684\u5143\u7d20\u5305\u542b\u5728\u5217\u8868\u4e2d\uff0c\u4e8c\u5206\u67e5\u627e\u8fd4\u56de\u5176\u4f4d\u7f6e\uff0c\u5426\u5219\u8fd4\u56denull\u3002 \u9996\u5148\u4ecb\u7ecd\u7b80\u5355\u67e5\u627e \u7b80\u5355\u67e5\u627e\u5c31\u662f\u2018\u50bb\u627e\u2019\uff0c\u4f8b\u5982\u731c\u6d4b\u4e00\u4e2a1~100\u7684\u6570\u5b57\uff0c\u4ece1\u5f00\u59cb\u4f9d\u6b21\u5f80\u4e0a\u731c\uff0c\u6bcf\u6b21\u731c\u6d4b\u53ea\u80fd\u6392\u9664\u4e00\u4e2a\u6570\u5b57\u3002\u5982\u679c\u6570\u5b57\u662f99\uff0c\u5219\u9700\u8981\u731c\u6d4b99\u6b21\u624d\u80fd\u731c\u5230\u3002 \u4e8c\u5206\u67e5\u627e \u800c\u4e8c\u5206\u67e5\u627e\u6cd5\u5219\u4ece50\u5f00\u59cb\uff0c\u4e00\u4e0b\u5b50\u53ef\u4ee5\u6392\u9664\u4e00\u534a\u7684\u6570\u5b57\uff1b\u6bcf\u6b21\u90fd\u731c\u6d4b\u4e2d\u95f4\u7684\u6570\u5b57\uff0c\u4ece\u800c\u6bcf\u6b21\u90fd\u5c06\u5269\u4f59\u7684\u6570\u5b57\u6392\u9664\u4e00\u534a\u3002 \u4e00\u822c\u800c\u8a00\uff0c\u5bf9\u4e8e\u5305\u542bn\u4e2a\u5143\u7d20\u7684\u5217\u8868\uff0c\u7528\u4e8c\u5206\u67e5\u627e\u6700\u591a\u9700\u8981[latex]\\log n[\/latex]\u6b65\uff0c\u800c\u7b80\u5355\u67e5\u627e\u6700\u591a\u9700\u8981n\u6b65\u3002 \u4e8c\u5206\u67e5\u627ePython\u4ee3\u7801\u5b9e\u73b0 def binary_search(list, item): low = 0 high = len(list) &#8211; 1 while low &lt;= high: #\u53ea\u8981\u8303\u56f4\u6ca1\u6709\u7f29\u5c0f\u5230\u53ea\u5305\u542b\u4e00\u4e2a\u5143\u7d20\uff0c\u5c31\u68c0\u67e5\u4e2d\u95f4\u7684\u5143\u7d20 mid = (low + high) \/\/ 2 guess = list[mid] if guess == item: #\u627e\u5230\u5143\u7d20\u4e86 return mid if guess &gt; item: #\u731c\u7684\u503c\u5927\u4e86 high = [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":75,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19,28],"tags":[10,27,29],"class_list":["post-74","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm","category-basic-concepts","tag-python","tag-27","tag-29"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.4 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>\u4e8c\u5206\u67e5\u627e\u548c\u5927O\u8868\u793a\u6cd5 - Nemo<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/nemo.cool\/74.html\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"\u4e8c\u5206\u67e5\u627e\u548c\u5927O\u8868\u793a\u6cd5 - Nemo\" \/>\n<meta property=\"og:description\" content=\"\u672c\u7ae0\u5185\u5bb9 \u7f16\u5199\u7b2c\u4e00\u79cd\u67e5\u627e\u7b97\u6cd5\uff1a\u4e8c\u5206\u67e5\u627e \u5b66\u4e60\u5982\u4f55\u8c08\u8bba\u7b97\u6cd5\u7684\u8fd0\u884c\u65f6\u95f4\uff1a\u5927O\u8868\u793a\u6cd5 \u4e86\u89e3\u4e00\u79cd\u5e38\u7528\u7684\u8bbe\u8ba1\u65b9\u6cd5\uff1a\u9012\u5f52 \u4ec0\u4e48\u662f\u7b97\u6cd5\uff1f \u7b97\u6cd5\u662f\u4e00\u7ec4\u5b8c\u6210\u4efb\u52a1\u7684\u6307\u4ee4\uff0c\u4efb\u4f55\u4ee3\u7801\u7247\u6bb5\u90fd\u53ef\u4ee5\u89c6\u4e3a\u7b97\u6cd5\u3002 \u4e8c\u5206\u67e5\u627e \u4e8c\u5206\u67e5\u627e\u662f\u4e00\u79cd\u7b97\u6cd5\uff0c\u5176\u8f93\u5165\u662f\u4e00\u4e2a\u6709\u5e8f\u7684\u5143\u7d20\u5217\u8868(\u4ec5\u5f53\u5217\u8868\u6709\u5e8f\u7684\u65f6\u5019\uff0c\u4e8c\u5206\u67e5\u627e\u624d\u7ba1\u7528)\u3002\u5982\u679c\u8981\u67e5\u627e\u7684\u5143\u7d20\u5305\u542b\u5728\u5217\u8868\u4e2d\uff0c\u4e8c\u5206\u67e5\u627e\u8fd4\u56de\u5176\u4f4d\u7f6e\uff0c\u5426\u5219\u8fd4\u56denull\u3002 \u9996\u5148\u4ecb\u7ecd\u7b80\u5355\u67e5\u627e \u7b80\u5355\u67e5\u627e\u5c31\u662f\u2018\u50bb\u627e\u2019\uff0c\u4f8b\u5982\u731c\u6d4b\u4e00\u4e2a1~100\u7684\u6570\u5b57\uff0c\u4ece1\u5f00\u59cb\u4f9d\u6b21\u5f80\u4e0a\u731c\uff0c\u6bcf\u6b21\u731c\u6d4b\u53ea\u80fd\u6392\u9664\u4e00\u4e2a\u6570\u5b57\u3002\u5982\u679c\u6570\u5b57\u662f99\uff0c\u5219\u9700\u8981\u731c\u6d4b99\u6b21\u624d\u80fd\u731c\u5230\u3002 \u4e8c\u5206\u67e5\u627e \u800c\u4e8c\u5206\u67e5\u627e\u6cd5\u5219\u4ece50\u5f00\u59cb\uff0c\u4e00\u4e0b\u5b50\u53ef\u4ee5\u6392\u9664\u4e00\u534a\u7684\u6570\u5b57\uff1b\u6bcf\u6b21\u90fd\u731c\u6d4b\u4e2d\u95f4\u7684\u6570\u5b57\uff0c\u4ece\u800c\u6bcf\u6b21\u90fd\u5c06\u5269\u4f59\u7684\u6570\u5b57\u6392\u9664\u4e00\u534a\u3002 \u4e00\u822c\u800c\u8a00\uff0c\u5bf9\u4e8e\u5305\u542bn\u4e2a\u5143\u7d20\u7684\u5217\u8868\uff0c\u7528\u4e8c\u5206\u67e5\u627e\u6700\u591a\u9700\u8981[latex]log n[\/latex]\u6b65\uff0c\u800c\u7b80\u5355\u67e5\u627e\u6700\u591a\u9700\u8981n\u6b65\u3002 \u4e8c\u5206\u67e5\u627ePython\u4ee3\u7801\u5b9e\u73b0 def binary_search(list, item): low = 0 high = len(list) - 1 while low &lt;= high: #\u53ea\u8981\u8303\u56f4\u6ca1\u6709\u7f29\u5c0f\u5230\u53ea\u5305\u542b\u4e00\u4e2a\u5143\u7d20\uff0c\u5c31\u68c0\u67e5\u4e2d\u95f4\u7684\u5143\u7d20 mid = (low + high) \/\/ 2 guess = list[mid] if guess == item: #\u627e\u5230\u5143\u7d20\u4e86 return mid if guess &gt; item: #\u731c\u7684\u503c\u5927\u4e86 high = [&hellip;]\" \/>\n<meta property=\"og:url\" content=\"https:\/\/nemo.cool\/74.html\" \/>\n<meta property=\"og:site_name\" content=\"Nemo\" \/>\n<meta property=\"article:published_time\" content=\"2019-05-12T13:55:59+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2020-06-24T08:22:25+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/nemo.cool\/wp-content\/uploads\/2019\/05\/timg-2.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"680\" \/>\n\t<meta property=\"og:image:height\" content=\"453\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"Nemo\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Nemo\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/74.html#article\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/74.html\"},\"author\":{\"name\":\"Nemo\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/#\\\/schema\\\/person\\\/698f803ee811e2b140a90f5d5de913d2\"},\"headline\":\"\u4e8c\u5206\u67e5\u627e\u548c\u5927O\u8868\u793a\u6cd5\",\"datePublished\":\"2019-05-12T13:55:59+00:00\",\"dateModified\":\"2020-06-24T08:22:25+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/74.html\"},\"wordCount\":43,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/#\\\/schema\\\/person\\\/698f803ee811e2b140a90f5d5de913d2\"},\"image\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/74.html#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2019\\\/05\\\/timg-2.jpg\",\"keywords\":[\"python\",\"\u4e8c\u5206\u67e5\u627e\",\"\u7b97\u6cd5\u56fe\u89e3\"],\"articleSection\":[\"Algorithm Notes\",\"Basic Concepts\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\\\/\\\/nemo.cool\\\/74.html#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/74.html\",\"url\":\"https:\\\/\\\/nemo.cool\\\/74.html\",\"name\":\"\u4e8c\u5206\u67e5\u627e\u548c\u5927O\u8868\u793a\u6cd5 - Nemo\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/74.html#primaryimage\"},\"image\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/74.html#primaryimage\"},\"thumbnailUrl\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2019\\\/05\\\/timg-2.jpg\",\"datePublished\":\"2019-05-12T13:55:59+00:00\",\"dateModified\":\"2020-06-24T08:22:25+00:00\",\"breadcrumb\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/74.html#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\\\/\\\/nemo.cool\\\/74.html\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/74.html#primaryimage\",\"url\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2019\\\/05\\\/timg-2.jpg\",\"contentUrl\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2019\\\/05\\\/timg-2.jpg\",\"width\":680,\"height\":453},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/74.html#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"\u9996\u9875\",\"item\":\"https:\\\/\\\/nemo.cool\\\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"\u4e8c\u5206\u67e5\u627e\u548c\u5927O\u8868\u793a\u6cd5\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/#website\",\"url\":\"https:\\\/\\\/nemo.cool\\\/\",\"name\":\"Nemo\",\"description\":\"\",\"publisher\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/#\\\/schema\\\/person\\\/698f803ee811e2b140a90f5d5de913d2\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\\\/\\\/nemo.cool\\\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\\\/\\\/nemo.cool\\\/#\\\/schema\\\/person\\\/698f803ee811e2b140a90f5d5de913d2\",\"name\":\"Nemo\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2024\\\/01\\\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg\",\"url\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2024\\\/01\\\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg\",\"contentUrl\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2024\\\/01\\\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg\",\"caption\":\"Nemo\"},\"logo\":{\"@id\":\"https:\\\/\\\/nemo.cool\\\/wp-content\\\/uploads\\\/2024\\\/01\\\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg\"},\"sameAs\":[\"https:\\\/\\\/nemo.cool\"]}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"\u4e8c\u5206\u67e5\u627e\u548c\u5927O\u8868\u793a\u6cd5 - Nemo","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/nemo.cool\/74.html","og_locale":"en_US","og_type":"article","og_title":"\u4e8c\u5206\u67e5\u627e\u548c\u5927O\u8868\u793a\u6cd5 - Nemo","og_description":"\u672c\u7ae0\u5185\u5bb9 \u7f16\u5199\u7b2c\u4e00\u79cd\u67e5\u627e\u7b97\u6cd5\uff1a\u4e8c\u5206\u67e5\u627e \u5b66\u4e60\u5982\u4f55\u8c08\u8bba\u7b97\u6cd5\u7684\u8fd0\u884c\u65f6\u95f4\uff1a\u5927O\u8868\u793a\u6cd5 \u4e86\u89e3\u4e00\u79cd\u5e38\u7528\u7684\u8bbe\u8ba1\u65b9\u6cd5\uff1a\u9012\u5f52 \u4ec0\u4e48\u662f\u7b97\u6cd5\uff1f \u7b97\u6cd5\u662f\u4e00\u7ec4\u5b8c\u6210\u4efb\u52a1\u7684\u6307\u4ee4\uff0c\u4efb\u4f55\u4ee3\u7801\u7247\u6bb5\u90fd\u53ef\u4ee5\u89c6\u4e3a\u7b97\u6cd5\u3002 \u4e8c\u5206\u67e5\u627e \u4e8c\u5206\u67e5\u627e\u662f\u4e00\u79cd\u7b97\u6cd5\uff0c\u5176\u8f93\u5165\u662f\u4e00\u4e2a\u6709\u5e8f\u7684\u5143\u7d20\u5217\u8868(\u4ec5\u5f53\u5217\u8868\u6709\u5e8f\u7684\u65f6\u5019\uff0c\u4e8c\u5206\u67e5\u627e\u624d\u7ba1\u7528)\u3002\u5982\u679c\u8981\u67e5\u627e\u7684\u5143\u7d20\u5305\u542b\u5728\u5217\u8868\u4e2d\uff0c\u4e8c\u5206\u67e5\u627e\u8fd4\u56de\u5176\u4f4d\u7f6e\uff0c\u5426\u5219\u8fd4\u56denull\u3002 \u9996\u5148\u4ecb\u7ecd\u7b80\u5355\u67e5\u627e \u7b80\u5355\u67e5\u627e\u5c31\u662f\u2018\u50bb\u627e\u2019\uff0c\u4f8b\u5982\u731c\u6d4b\u4e00\u4e2a1~100\u7684\u6570\u5b57\uff0c\u4ece1\u5f00\u59cb\u4f9d\u6b21\u5f80\u4e0a\u731c\uff0c\u6bcf\u6b21\u731c\u6d4b\u53ea\u80fd\u6392\u9664\u4e00\u4e2a\u6570\u5b57\u3002\u5982\u679c\u6570\u5b57\u662f99\uff0c\u5219\u9700\u8981\u731c\u6d4b99\u6b21\u624d\u80fd\u731c\u5230\u3002 \u4e8c\u5206\u67e5\u627e \u800c\u4e8c\u5206\u67e5\u627e\u6cd5\u5219\u4ece50\u5f00\u59cb\uff0c\u4e00\u4e0b\u5b50\u53ef\u4ee5\u6392\u9664\u4e00\u534a\u7684\u6570\u5b57\uff1b\u6bcf\u6b21\u90fd\u731c\u6d4b\u4e2d\u95f4\u7684\u6570\u5b57\uff0c\u4ece\u800c\u6bcf\u6b21\u90fd\u5c06\u5269\u4f59\u7684\u6570\u5b57\u6392\u9664\u4e00\u534a\u3002 \u4e00\u822c\u800c\u8a00\uff0c\u5bf9\u4e8e\u5305\u542bn\u4e2a\u5143\u7d20\u7684\u5217\u8868\uff0c\u7528\u4e8c\u5206\u67e5\u627e\u6700\u591a\u9700\u8981[latex]log n[\/latex]\u6b65\uff0c\u800c\u7b80\u5355\u67e5\u627e\u6700\u591a\u9700\u8981n\u6b65\u3002 \u4e8c\u5206\u67e5\u627ePython\u4ee3\u7801\u5b9e\u73b0 def binary_search(list, item): low = 0 high = len(list) - 1 while low &lt;= high: #\u53ea\u8981\u8303\u56f4\u6ca1\u6709\u7f29\u5c0f\u5230\u53ea\u5305\u542b\u4e00\u4e2a\u5143\u7d20\uff0c\u5c31\u68c0\u67e5\u4e2d\u95f4\u7684\u5143\u7d20 mid = (low + high) \/\/ 2 guess = list[mid] if guess == item: #\u627e\u5230\u5143\u7d20\u4e86 return mid if guess &gt; item: #\u731c\u7684\u503c\u5927\u4e86 high = [&hellip;]","og_url":"https:\/\/nemo.cool\/74.html","og_site_name":"Nemo","article_published_time":"2019-05-12T13:55:59+00:00","article_modified_time":"2020-06-24T08:22:25+00:00","og_image":[{"width":680,"height":453,"url":"https:\/\/nemo.cool\/wp-content\/uploads\/2019\/05\/timg-2.jpg","type":"image\/jpeg"}],"author":"Nemo","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Nemo"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/nemo.cool\/74.html#article","isPartOf":{"@id":"https:\/\/nemo.cool\/74.html"},"author":{"name":"Nemo","@id":"https:\/\/nemo.cool\/#\/schema\/person\/698f803ee811e2b140a90f5d5de913d2"},"headline":"\u4e8c\u5206\u67e5\u627e\u548c\u5927O\u8868\u793a\u6cd5","datePublished":"2019-05-12T13:55:59+00:00","dateModified":"2020-06-24T08:22:25+00:00","mainEntityOfPage":{"@id":"https:\/\/nemo.cool\/74.html"},"wordCount":43,"commentCount":0,"publisher":{"@id":"https:\/\/nemo.cool\/#\/schema\/person\/698f803ee811e2b140a90f5d5de913d2"},"image":{"@id":"https:\/\/nemo.cool\/74.html#primaryimage"},"thumbnailUrl":"https:\/\/nemo.cool\/wp-content\/uploads\/2019\/05\/timg-2.jpg","keywords":["python","\u4e8c\u5206\u67e5\u627e","\u7b97\u6cd5\u56fe\u89e3"],"articleSection":["Algorithm Notes","Basic Concepts"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/nemo.cool\/74.html#respond"]}]},{"@type":"WebPage","@id":"https:\/\/nemo.cool\/74.html","url":"https:\/\/nemo.cool\/74.html","name":"\u4e8c\u5206\u67e5\u627e\u548c\u5927O\u8868\u793a\u6cd5 - Nemo","isPartOf":{"@id":"https:\/\/nemo.cool\/#website"},"primaryImageOfPage":{"@id":"https:\/\/nemo.cool\/74.html#primaryimage"},"image":{"@id":"https:\/\/nemo.cool\/74.html#primaryimage"},"thumbnailUrl":"https:\/\/nemo.cool\/wp-content\/uploads\/2019\/05\/timg-2.jpg","datePublished":"2019-05-12T13:55:59+00:00","dateModified":"2020-06-24T08:22:25+00:00","breadcrumb":{"@id":"https:\/\/nemo.cool\/74.html#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/nemo.cool\/74.html"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/nemo.cool\/74.html#primaryimage","url":"https:\/\/nemo.cool\/wp-content\/uploads\/2019\/05\/timg-2.jpg","contentUrl":"https:\/\/nemo.cool\/wp-content\/uploads\/2019\/05\/timg-2.jpg","width":680,"height":453},{"@type":"BreadcrumbList","@id":"https:\/\/nemo.cool\/74.html#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"\u9996\u9875","item":"https:\/\/nemo.cool\/"},{"@type":"ListItem","position":2,"name":"\u4e8c\u5206\u67e5\u627e\u548c\u5927O\u8868\u793a\u6cd5"}]},{"@type":"WebSite","@id":"https:\/\/nemo.cool\/#website","url":"https:\/\/nemo.cool\/","name":"Nemo","description":"","publisher":{"@id":"https:\/\/nemo.cool\/#\/schema\/person\/698f803ee811e2b140a90f5d5de913d2"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/nemo.cool\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/nemo.cool\/#\/schema\/person\/698f803ee811e2b140a90f5d5de913d2","name":"Nemo","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/nemo.cool\/wp-content\/uploads\/2024\/01\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg","url":"https:\/\/nemo.cool\/wp-content\/uploads\/2024\/01\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg","contentUrl":"https:\/\/nemo.cool\/wp-content\/uploads\/2024\/01\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg","caption":"Nemo"},"logo":{"@id":"https:\/\/nemo.cool\/wp-content\/uploads\/2024\/01\/Big_Hero_6_Anime_HD_desktop_wallpaper_01_1366x768-e1706020097529-96x96.jpg"},"sameAs":["https:\/\/nemo.cool"]}]}},"_links":{"self":[{"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/posts\/74","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/comments?post=74"}],"version-history":[{"count":0,"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/posts\/74\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/media\/75"}],"wp:attachment":[{"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/media?parent=74"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/categories?post=74"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nemo.cool\/wp-json\/wp\/v2\/tags?post=74"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}