Find in mountain array

Array Binary Search Interactive

41.2% acceptance

Feb 25, 2026

3582

155

(This problem is an interactive problem.) You may recall that an array arr is a mountain array if and only if: arr.length >= 3 There exists some i with 0 < i < arr.length - 1 such that: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ... > arr[arr.length - 1] Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index does not exist, return -1. You cannot access the mountain array directly. You may only access the array using a MountainArray interface: MountainArray.get(k) returns the element of the array at index k (0-indexed). MountainArray.length() returns the length of the array. Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer. Also, any solutions that attempt to circumvent the judge will result in disqualification.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

*/

impl Solution {
  pub fn find_in_mountain_array(target: i32, mountain_arr: &MountainArray) -> i32 {
    let n = mountain_arr.length() as usize;
    // Find peak
    let (mut lo, mut hi) = (0usize, n - 1);
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if mountain_arr.get(mid as i32) < mountain_arr.get(mid as i32 + 1) {
        lo = mid + 1;
      } else {
        hi = mid;
      }
    }
    let peak = lo;
    // Search ascending part [0, peak]
    let (mut lo, mut hi) = (0usize, peak);
    while lo <= hi {
      let mid = lo + (hi - lo) / 2;
      let v = mountain_arr.get(mid as i32);
      if v == target { return mid as i32; }
      else if v < target { lo = mid + 1; }
      else { if mid == 0 { break; } hi = mid - 1; }
    }
    // Search descending part [peak, n-1]
    let (mut lo, mut hi) = (peak, n - 1);
    while lo <= hi {
      let mid = lo + (hi - lo) / 2;
      let v = mountain_arr.get(mid as i32);
      if v == target { return mid as i32; }
      else if v > target { lo = mid + 1; }
      else { if mid == 0 { break; } hi = mid - 1; }
    }
    -1
  }
}