Find in Mountain Array

hard binary search mountain array array

Problem

A mountain array strictly increases to a single peak and then strictly decreases. Given such an array, return the minimum index whose value equals target, or -1 if it is absent. First binary-search for the peak, then binary-search the ascending half (prefer it for the smallest index) and, if needed, the descending half.

Inputarr = [1, 2, 3, 4, 5, 3, 1], target = 3

Output2

Value 3 appears at indices 2 and 5; the smallest index 2 lies on the ascending slope, so we return it.

arr (mountain, comma-separated)

target

def find_in_mountain_array(target, arr):
    n = len(arr)
    lo, hi = 0, n - 1
    while lo < hi:                       # locate the peak
        mid = (lo + hi) // 2
        if arr[mid] < arr[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    peak = lo
    lo, hi = 0, peak                     # ascending search
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    lo, hi = peak + 1, n - 1             # descending search
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] > target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

function findInMountainArray(target, arr) {
  const n = arr.length;
  let lo = 0, hi = n - 1;
  while (lo < hi) {                      // locate the peak
    const mid = (lo + hi) >> 1;
    if (arr[mid] < arr[mid + 1]) lo = mid + 1;
    else hi = mid;
  }
  const peak = lo;
  lo = 0; hi = peak;                      // ascending search
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  lo = peak + 1; hi = n - 1;              // descending search
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] === target) return mid;
    if (arr[mid] > target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

class Solution {
    public int findInMountainArray(int target, int[] arr) {
        int n = arr.length, lo = 0, hi = n - 1;
        while (lo < hi) {                      // locate the peak
            int mid = (lo + hi) >>> 1;
            if (arr[mid] < arr[mid + 1]) lo = mid + 1;
            else hi = mid;
        }
        int peak = lo;
        lo = 0; hi = peak;                      // ascending search
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        lo = peak + 1; hi = n - 1;              // descending search
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (arr[mid] == target) return mid;
            if (arr[mid] > target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }
}

int findInMountainArray(int target, vector<int>& arr) {
    int n = arr.size(), lo = 0, hi = n - 1;
    while (lo < hi) {                      // locate the peak
        int mid = (lo + hi) / 2;
        if (arr[mid] < arr[mid + 1]) lo = mid + 1;
        else hi = mid;
    }
    int peak = lo;
    lo = 0; hi = peak;                      // ascending search
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    lo = peak + 1; hi = n - 1;              // descending search
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] > target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Explanation

A mountain array goes up then down, so it is not fully sorted — but each half is. The trick is to first find the peak, which splits the array into a clean ascending part and a clean descending part, and then binary-search those halves.

To find the peak, we binary-search comparing arr[mid] with its right neighbour arr[mid + 1]. If we are still climbing (arr[mid] < arr[mid+1]), the peak is further right, so lo = mid + 1; otherwise it is at mid or left, so hi = mid. The loop lands on the peak index.

We then binary-search the ascending half first, because the problem wants the smallest index and that half holds the earlier positions. A normal ascending binary search applies. If the target is not there, we search the descending half, where the comparison is flipped (go right when arr[mid] > target).

Example: arr = [1,2,3,4,5,3,1], target = 3. The peak is index 4 (value 5). Searching [0..4] finds 3 at index 2, which is the smallest index, so we return 2 without even touching the right half.

Three binary searches, each O(log n), give an overall O(log n) solution.

Time: O(log n) Space: O(1)