{"id":1874,"date":"2016-03-13T19:51:56","date_gmt":"2016-03-13T11:51:56","guid":{"rendered":"http:\/\/boweihe.me\/?p=1874"},"modified":"2016-03-13T19:51:56","modified_gmt":"2016-03-13T11:51:56","slug":"leetcode-34-search-for-a-range","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1874","title":{"rendered":"LeetCode 34. Search for a Range"},"content":{"rendered":"<p><strong>\u9898\u76ee\uff1a<\/strong><a href=\"https:\/\/leetcode.com\/problems\/search-for-a-range\/\" target=\"_blank\" rel=\"noopener noreferrer\">https:\/\/leetcode.com\/problems\/search-for-a-range\/<\/a><br \/>\n<strong>\u601d\u8def\uff1a<\/strong>\u770bLogN\u7ea7\u522b\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u8981\u6c42\u5c31\u5e94\u8be5\u53ef\u4ee5\u60f3\u5230\u8981\u7528\u4e8c\u5206\u67e5\u627e\u7c7b\u4f3c\u7684\u505a\uff0c\u5173\u952e\u95ee\u9898\u662f\u6709\u91cd\u590d\u5143\u7d20\uff0c\u5c31\u662f\u8bf4\u5982\u679c\u627e\u5230\u4e86a[i]==target\uff0c\u8fd8\u5f97\u987e\u53ca\u4e00\u4e0b\u4ed6\u7684\u5de6\u53f3\u90bb\u5c45\u7684\u503c\u662f\u4e0d\u662f\u4e5f\u4e00\u6837\u7684\uff0c\u5982\u679c\u662f\u7684\u8bdd\uff0c\u90a3\u8bf4\u660e\u8fd8\u5f97\u7ee7\u7eed\u627e<br \/>\n<strong>\u4ee3\u7801\uff1a<\/strong><\/p>\n<pre class=\"lang:c++ decode:true \">class Solution {\npublic:\n    int searchMin(vector&lt;int&gt;&amp; nums, int target) {\n        int l = 0;\n        int r = nums.size() - 1;\n        int m;\n        while (l &lt;= r) {\n            m = (l + r)\/2;\n            if(nums[m] == target){\n                if(m == 0)\n                    return m;\n                else if(nums[m-1] &lt; target) \/\/targst cannot be in the left part\n                    return m;\n                else {\n                    r = m - 1;\n                }\n            } else if(nums[m] &lt; target) {\n                l = m + 1;\n            } else {\n                r = m - 1;\n            }\n        }\n        return -1;\n    }\n    int searchMax(vector&lt;int&gt;&amp; nums, int target) {\n        int l=0;\n        int r = nums.size() - 1;\n        int m;\n        while(l &lt;= r) {\n            m = (l + r)\/2;\n            if(nums[m] == target){\n                if (m == r)\n                    return m;\n                else if(nums[m+1] &gt; target)\n                    return m;\n                else\n                    l = m + 1;\n            } else if (nums[m] &lt; target) {\n                l = m + 1;\n            } else {\n                r = m - 1;\n            }\n        }\n        return -1;\n    }\n    vector&lt;int&gt; searchRange(vector&lt;int&gt;&amp; nums, int target) {\n        vector&lt;int&gt; result;\n        result.push_back(searchMin(nums, target));\n        result.push_back(searchMax(nums, target));\n        return result;\n    }\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\uff1ahttps:\/\/leetcode.com\/problems\/search-for-a-range\/ \u601d\u8def\uff1a\u770bLogN\u7ea7\u522b\u65f6\u95f4\u590d\u6742\u5ea6\u7684\u8981\u6c42\u5c31\u5e94\u8be5\u53ef\u4ee5\u60f3\u5230\u8981\u7528\u4e8c\u5206\u67e5\u627e\u7c7b\u4f3c\u7684\u505a\uff0c\u5173\u952e\u95ee\u9898\u662f\u6709\u91cd\u590d\u5143\u7d20\uff0c\u5c31\u662f\u8bf4\u5982\u679c\u627e\u5230\u4e86a[i]==target\uff0c\u8fd8\u5f97\u987e\u53ca\u4e00\u4e0b\u4ed6\u7684\u5de6\u53f3\u90bb\u5c45\u7684\u503c\u662f\u4e0d\u662f\u4e5f\u4e00\u6837\u7684\uff0c\u5982\u679c\u662f\u7684\u8bdd\uff0c\u90a3\u8bf4\u660e\u8fd8\u5f97\u7ee7\u7eed\u627e \u4ee3\u7801\uff1a class Solution { public: int searchMin(vector&lt;int&gt;&amp; nums, int target) { int l = 0; int r = nums.size() &#8211; 1; int m; while (l &lt;= r) { m = (l + r)\/2; if(nums[m] == target){ if(m == 0) return m; else if(nums[m-1] &lt; target) \/\/targst cannot be in the left part return [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66],"class_list":["post-1874","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1874","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1874"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1874\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1874"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1874"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1874"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}