{"id":905,"date":"2021-04-28T22:28:59","date_gmt":"2021-04-29T05:28:59","guid":{"rendered":"http:\/\/cywang.no-ip.org\/wordpress\/?p=905"},"modified":"2021-05-10T22:40:04","modified_gmt":"2021-05-11T05:40:04","slug":"704-binary-search","status":"publish","type":"post","link":"http:\/\/cywang.no-ip.org\/wordpress\/?p=905","title":{"rendered":"704. Binary Search"},"content":{"rendered":"<p>704. Binary Search<\/p>\n<p><!--more--><\/p>\n<pre class=\"line-numbers\"><code class=\"language-python\"># Approach. Binary Search\r\n# Time Complexity: O(log n)\r\n# Space Complexity: O(1)\r\nclass Solution:\r\n    def search(self, nums: List[int], target: int) -&gt; int:\r\n        if len(nums) == 0:\r\n            return -1\r\n        left_index = 0\r\n        right_index = len(nums) - 1\r\n        while left_index &lt;= right_index:\r\n            middle_index = (left_index + right_index) \/\/ 2\r\n            if nums[middle_index] &lt; target:     # right part\r\n                left_index = middle_index + 1\r\n            elif nums[middle_index] &gt; target:   # left part\r\n                right_index = middle_index - 1\r\n            else:   # found\r\n                return middle_index\r\n\r\n        return -1<\/code><\/pre>\n<hr \/>\n<h1>Notes:<\/h1>\n<p>\u7a0b\u5f0f\u6d41\u7a0b<\/p>\n<ul>\n<li>\u56e0\u70ba\u984c\u76ee\u4e2d\u63d0\u5230nums\u662f\u4e00\u500b\u905e\u589e\u9663\u5217\uff0c\u6240\u4ee5\u53ef\u4ee5\u7528binary search \u627e\u5230\u89e3 (\u5982\u679c\u5b58\u5728)\uff0c\u800cbinary search \u7684 time complexity\u70ba O(log n)<\/li>\n<li>Pseudo-code\n<pre class=\"line-numbers\">left_index = 0 # \u521d\u59cb\u5316\u5de6\u908a\u7684index\r\nright_index = length - 1 # \u521d\u59cb\u5316\u53f3\u908a\u7684index (\u56e0\u70baarray\u7684index 0\u958b\u59cb\uff0c\u6240\u4ee5right_index\u70ba\u9577\u5ea6\u6e1b1)\r\nwhile left_index &lt;= right_index : # \u8dd1\u8ff4\u5708\uff0c\u76f4\u5230 left_index &gt; right_index\u96e2\u958b\uff0c\u8868\u793a\u6c92\u627e\u5230target\r\n    middle_index = (left + right) \/\/ 2\r\n    middle = nums[middle_index)\r\n    \u82e5\u4e2d\u9593\u503c(middle)\u5c0f\u65bctarget -&gt; target\u5728\u53f3\u534a\u908a\uff0c left_index = middle_index + 1\r\n    \u82e5\u4e2d\u9593\u503c(middle)\u5927\u65bctarget -&gt; target\u5728\u5de6\u534a\u908a\uff0c right_index = middle_index -1\r\n    \u82e5\u524d\u5169\u500b\u689d\u4ef6\u90fd\u4e0d\u6210\u7acb\uff0c\u8868\u793amiddle\u7b49\u65bctarget -&gt; \u627e\u5230target\uff0creturn middle_index\r\n\u82e5\u96e2\u958bwhile loop\u90fd\u6c92\u56de\u50b3\u7d50\u679c\uff0c\u8868\u793a\u6c92\u627e\u5230target\uff0creturn -1<\/pre>\n<\/li>\n<\/ul>\n<p>\u7d00\u9304<\/p>\n<ul>\n<li>5\u5206\u9418 \uff1a \u4e86\u89e3\u984c\u76ee (assumptions\u3001work through examples, function signature)<\/li>\n<li>2-3\u5206\u9418 \uff1a \u8003\u616ebrute force solution (O(n))\uff0c\u5df2\u77e5\u9663\u5217\u662f\u905e\u589e\u4e14\u6392\u5e8f\uff0c\u4e0d\u53ef\u80fd\u7528\u66b4\u529b\u89e3\u6cd5\uff0c\u6240\u4ee5\u4e26\u672a\u5be6\u4f5c\uff0c\u4e26\u6839\u64da\u984c\u76ee\u7d66\u7684\u689d\u4ef6\uff0c\u61c9\u8a72\u7528binary search\u7684\u65b9\u5f0f\u5be6\u4f5c(O(log n))<\/li>\n<li>15\u5206\u9418\u5beb\u4e0bpseudo code\uff0c\u4e26\u8f49\u6210Python code\uff0c\u8209\u5e7e\u500b\u4f8b\u5b50\u7528\u624b\u5beb(\u6a21\u64ec)\u7684\u65b9\u5f0f\u8dd1\u904e\u4e00\u6b21\u7a0b\u5f0f\u78bc<\/li>\n<li>5\u5206\u9418\uff1a\u628a\u624b\u5beb\u7684\u7a0b\u5f0f\u78bc\u8f38\u5165Leetcode\u4e26\u57f7\u884c<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>\u5099\u8a3b<\/p>\n<ul>\n<li>\u5728\u7b2c\u4e00\u6b21\u6a21\u64ec\u7a0b\u5f0f\u57f7\u884c\u904e\u7a0b\u4e2d\uff0c\u767c\u73fe\u6211\u7684\u7b2c\u4e00\u7248\u7a0b\u5f0f\u6709bug\uff0cwhile loop\u7684\u689d\u4ef6\u61c9\u8a72\u662f left &lt;= right\uff0c\u4f46\u662f\u6211\u5beb\u6210left &lt; right<\/li>\n<li>\u96e3\u5ea6\u4e0a\u4f86\u8aaa\uff0c\u4ecb\u65bc\u904e\u65bc\u7c21\u55ae\u8ddf\u96e3\u5ea6\u9069\u4e2d\u4e4b\u9593\uff0c\u56e0\u70ba\u7b2c\u4e00\u7248\u6709bug\uff0c\u8868\u793a\u6211\u4e00\u958b\u59cb\u4e26\u672a\u8003\u616e\u5230\u6240\u6709\u60c5\u6cc1\uff0c\u6240\u4ee5\u9078\u64c7\u96e3\u5ea6\u9069\u4e2d<\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>704. Binary Search<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_exactmetrics_skip_tracking":false,"_exactmetrics_sitenote_active":false,"_exactmetrics_sitenote_note":"","_exactmetrics_sitenote_category":0,"footnotes":""},"categories":[39],"tags":[],"class_list":["post-905","post","type-post","status-publish","format-standard","hentry","category-leetcode"],"_links":{"self":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/905","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=905"}],"version-history":[{"count":3,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/905\/revisions"}],"predecessor-version":[{"id":920,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=\/wp\/v2\/posts\/905\/revisions\/920"}],"wp:attachment":[{"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=905"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=905"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/cywang.no-ip.org\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=905"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}