Find Peak Element

Medium Searching & Sorting

Return the index of a peak element (greater than its neighbours) using binary search in O(log n).

Sample input

[1, 2, 3, 1]

Sample output

Solution

def find_peak(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

print(find_peak([1, 2, 3, 1]))

function findPeak(nums) {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] < nums[mid + 1]) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

console.log(findPeak([1, 2, 3, 1]));

public class Main {
    static int findPeak(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] < nums[mid + 1]) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    public static void main(String[] args) {
        System.out.println(findPeak(new int[]{1, 2, 3, 1}));
    }
}

fun findPeak(nums: IntArray): Int {
    var lo = 0
    var hi = nums.size - 1
    while (lo < hi) {
        val mid = (lo + hi) / 2
        if (nums[mid] < nums[mid + 1]) lo = mid + 1 else hi = mid
    }
    return lo
}

fun main() {
    println(findPeak(intArrayOf(1, 2, 3, 1)))
}

func findPeak(_ nums: [Int]) -> Int {
    var lo = 0, hi = nums.count - 1
    while lo < hi {
        let mid = (lo + hi) / 2
        if nums[mid] < nums[mid + 1] {
            lo = mid + 1
        } else {
            hi = mid
        }
    }
    return lo
}

print(findPeak([1, 2, 3, 1]))

int findPeak(List<int> nums) {
  int lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    int mid = (lo + hi) ~/ 2;
    if (nums[mid] < nums[mid + 1]) {
      lo = mid + 1;
    } else {
      hi = mid;
    }
  }
  return lo;
}

void main() {
  print(findPeak([1, 2, 3, 1]));
}

#include <iostream>
#include <vector>
using namespace std;

int findPeak(const vector<int>& nums) {
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (nums[mid] < nums[mid + 1]) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

int main() {
    cout << findPeak({1, 2, 3, 1}) << endl;
    return 0;
}

#include <stdio.h>

int findPeak(int *nums, int n) {
    int lo = 0, hi = n - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (nums[mid] < nums[mid + 1]) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

int main() {
    int nums[] = {1, 2, 3, 1};
    printf("%d\n", findPeak(nums, 4));
    return 0;
}