{
 "cells": [
  {
   "cell_type": "markdown",
   "source": [
    "_(This problem is an   **interactive problem**.)_\n",
    "\n",
    "You may recall that an array `A` is a _mountain array_ if and only if:\n",
    "\n",
    "  * `A.length >= 3`\n",
    "  * There exists some `i` with `0 < i < A.length - 1` such that:\n",
    "    * `A[0] < A[1] < ... A[i-1] < A[i]`\n",
    "    * `A[i] > A[i+1] > ... > A[A.length - 1]`\n",
    "\n",
    "Given a mountain array `mountainArr`, return the **minimum**  `index` such\n",
    "that `mountainArr.get(index) == target`.  If such an `index` doesn't exist,\n",
    "return `-1`.\n",
    "\n",
    "**You can 't access the mountain array directly.**  You may only access the\n",
    "array using a `MountainArray` interface:\n",
    "\n",
    "  * `MountainArray.get(k)` returns the element of the array at index `k` (0-indexed).\n",
    "  * `MountainArray.length()` returns the length of the array.\n",
    "\n",
    "Submissions making more than `100` calls to `MountainArray.get` will be judged\n",
    "_Wrong Answer_.  Also, any solutions that attempt to circumvent the judge will\n",
    "result in disqualification.\n",
    "\n",
    "\n",
    "\n",
    "**Example 1:**\n",
    "\n",
    "\n",
    "\n",
    "    Input: array = [1,2,3,4,5,3,1], target = 3\n",
    "    Output: 2\n",
    "    Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.\n",
    "\n",
    "**Example 2:**\n",
    "\n",
    "\n",
    "\n",
    "    Input: array = [0,1,2,4,2,1], target = 3\n",
    "    Output: -1\n",
    "    Explanation: 3 does not exist in the array, so we return -1.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "**Constraints:**\n",
    "\n",
    "  * `3 <= mountain_arr.length() <= 10000`\n",
    "  * `0 <= target <= 10^9`\n",
    "  * `0 <= mountain_arr.get(index) <= 10^9`"
   ],
   "metadata": {}
  },
  {
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "find_in_mountain_array (generic function with 1 method)"
     },
     "metadata": {},
     "execution_count": 1
    }
   ],
   "cell_type": "code",
   "source": [
    "# @lc code=start\n",
    "using LeetCode\n",
    "\n",
    "struct MountainArray\n",
    "    vec::Vector{Int}\n",
    "end\n",
    "\n",
    "Base.length(ma::MountainArray) = length(ma.vec)\n",
    "Base.getindex(ma::MountainArray, i) = ma.vec[i]\n",
    "\n",
    "function find_in_mountain_array(ma::MountainArray, target::Int)\n",
    "    len = length(ma)\n",
    "    i, j = 1, len\n",
    "    while i != j\n",
    "        mid = (i + j) >> 1\n",
    "        ma[mid] > ma[mid + 1] ? (j = mid) : (i = mid + 1)\n",
    "    end\n",
    "    idx1 = searchsortedfirst(1:i, i; by=i -> ma[i] >= target)\n",
    "    ma[idx1] == target && return idx1\n",
    "    idx2 = searchsortedfirst((i + 1):len, i; by=i -> ma[i] <= target) + i\n",
    "    ma[idx2] == target && return idx2\n",
    "    return -1\n",
    "end\n",
    "# @lc code=end"
   ],
   "metadata": {},
   "execution_count": 1
  },
  {
   "cell_type": "markdown",
   "source": [
    "---\n",
    "\n",
    "*This notebook was generated using [Literate.jl](https://github.com/fredrikekre/Literate.jl).*"
   ],
   "metadata": {}
  }
 ],
 "nbformat_minor": 3,
 "metadata": {
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.1"
  },
  "kernelspec": {
   "name": "julia-1.10",
   "display_name": "Julia 1.10.1",
   "language": "julia"
  }
 },
 "nbformat": 4
}