{"id":7638,"date":"2020-11-13T21:57:59","date_gmt":"2020-11-14T05:57:59","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7638"},"modified":"2020-11-13T22:49:29","modified_gmt":"2020-11-14T06:49:29","slug":"1095-find-in-mountain-array","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/1095-find-in-mountain-array\/","title":{"rendered":"\u82b1\u82b1\u9171 1095. Find in Mountain Array &#8211; EP369"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1095. Find in Mountain Array - \u5237\u9898\u627e\u5de5\u4f5c EP369\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/G5IDEoX9bT0?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p><em>(This problem is an&nbsp;<strong>interactive problem<\/strong>.)<\/em><\/p>\n\n\n\n<p>You may recall that an array&nbsp;<code>A<\/code>&nbsp;is a&nbsp;<em>mountain array<\/em>&nbsp;if and only if:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>A.length &gt;= 3<\/code><\/li><li>There exists some&nbsp;<code>i<\/code>&nbsp;with&nbsp;<code>0 &lt; i&nbsp;&lt; A.length - 1<\/code>&nbsp;such that:<ul><li><code>A[0] &lt; A[1] &lt; ... A[i-1] &lt; A[i]<\/code><\/li><li><code>A[i] &gt; A[i+1] &gt; ... &gt; A[A.length - 1]<\/code><\/li><\/ul><\/li><\/ul>\n\n\n\n<p>Given a mountain&nbsp;array&nbsp;<code>mountainArr<\/code>, return the&nbsp;<strong>minimum<\/strong>&nbsp;<code>index<\/code>&nbsp;such that&nbsp;<code>mountainArr.get(index) == target<\/code>.&nbsp; If such an&nbsp;<code>index<\/code>&nbsp;doesn&#8217;t exist, return&nbsp;<code>-1<\/code>.<\/p>\n\n\n\n<p><strong>You can&#8217;t access the mountain array directly.<\/strong>&nbsp; You may only access the array using a&nbsp;<code>MountainArray<\/code>&nbsp;interface:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>MountainArray.get(k)<\/code>&nbsp;returns the element of the array at index&nbsp;<code>k<\/code>&nbsp;(0-indexed).<\/li><li><code>MountainArray.length()<\/code>&nbsp;returns the length of the array.<\/li><\/ul>\n\n\n\n<p>Submissions making more than&nbsp;<code>100<\/code>&nbsp;calls to&nbsp;<code>MountainArray.get<\/code>&nbsp;will be judged&nbsp;<em>Wrong Answer<\/em>.&nbsp; Also, any solutions that attempt to circumvent the judge&nbsp;will result in disqualification.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> array = [1,2,3,4,5,3,1], target = 3\n<strong>Output:<\/strong> 2\n<strong>Explanation:<\/strong> 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> array = [0,1,2,4,2,1], target = 3\n<strong>Output:<\/strong> -1\n<strong>Explanation:<\/strong> 3 does not exist in <code>the array,<\/code> so we return -1.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>3 &lt;= mountain_arr.length() &lt;= 10000<\/code><\/li><li><code>0 &lt;= target &lt;= 10^9<\/code><\/li><li><code>0 &lt;= mountain_arr.get(index) &lt;=&nbsp;10^9<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Binary Search<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1095-ep369.png\" alt=\"\" class=\"wp-image-7641\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1095-ep369.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1095-ep369-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/1095-ep369-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<ol class=\"wp-block-list\"><li>Find the peak index of the mountain array using binary search.<\/li><li>Perform two binary searches in two sorted subarrays (ascending one and descending one)<\/li><\/ol>\n\n\n\n<p>Time complexity: O(logn)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution {\npublic:\n  int findInMountainArray(int target, MountainArray &mountainArr) {\n    const int n = mountainArr.length();\n    \n    auto binary_search = [&](int l, int r, function<bool(int)> cond) {\n      while (l < r) {\n        int m = l + (r - l) \/ 2;\n        if (cond(m)) r = m;\n        else l = m + 1;\n      }  \n      return l;\n    };\n    \n    int p = binary_search(0, n - 1, [&#038;](int i) -> bool {\n      return mountainArr.get(i) > mountainArr.get(i + 1);\n    });    \n    \n    \/\/ if (target > mountainArr.get(p)) return -1;\n    \/\/ if (target == mountainArr.get(p)) return p;\n    \n    int l = binary_search(0, p, [&](int i) -> bool {\n      return mountainArr.get(i) >= target;\n    });\n    \n    if (mountainArr.get(l) == target) return l;\n    \n    int r = binary_search(p, n - 1, [&](int i) -> bool {\n      return mountainArr.get(i) <= target;\n    });        \n    \n    if (mountainArr.get(r) == target) return r;\n    \n    return -1;\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\nclass Solution:\n  def findInMountainArray(self, target: int, arr: 'MountainArray') -> int:\n    def binary_search(l, r, cond):\n      while l < r:\n        m = l + (r - l) \/\/ 2\n        if cond(m): r = m\n        else: l = m + 1\n      return l\n    \n    n = arr.length()    \n    p = binary_search(0, n - 1, lambda i: arr.get(i) > arr.get(i + 1))\n    l = binary_search(0, p, lambda i: arr.get(i) >= target)\n    if arr.get(l) == target: return l\n    r = binary_search(p, n - 1, lambda i: arr.get(i) <= target)\n    if arr.get(r) == target: return r\n    return -1\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>(This problem is an&nbsp;interactive problem.) You may recall that an array&nbsp;A&nbsp;is a&nbsp;mountain array&nbsp;if and only if: A.length &gt;= 3 There exists some&nbsp;i&nbsp;with&nbsp;0 &lt; i&nbsp;&lt; A.length&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[149],"tags":[52,217,253],"class_list":["post-7638","post","type-post","status-publish","format-standard","hentry","category-binary-search","tag-binary-search","tag-hard","tag-interactive","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7638","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7638"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7638\/revisions"}],"predecessor-version":[{"id":7643,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7638\/revisions\/7643"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7638"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7638"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7638"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}