Dada una array de enteros. Encuentra un elemento pico en él. Un elemento de array es un pico si NO es más pequeño que sus vecinos. Para elementos de esquina, debemos considerar solo un vecino.
Ejemplo:
C++
// A C++ program to find a peak element
#include <bits/stdc++.h>
using namespace std;
// Find the peak element in the array
int findPeak(int arr[], int n)
{
// first or last element is peak element
if (n == 1)
return 0;
if (arr[0] >= arr[1])
return 0;
if (arr[n - 1] >= arr[n - 2])
return n - 1;
// check for every other element
for (int i = 1; i < n - 1; i++) {
// check if the neighbors are smaller
if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1])
return i;
}
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Index of a peak point is " << findPeak(arr, n);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// A C program to find a peak element
#include <stdio.h>
// Find the peak element in the array
int findPeak(int arr[], int n)
{
// first or last element is peak element
if (n == 1)
return 0;
if (arr[0] >= arr[1])
return 0;
if (arr[n - 1] >= arr[n - 2])
return n - 1;
// check for every other element
for (int i = 1; i < n - 1; i++) {
// check if the neighbors are smaller
if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1])
return i;
}
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Index of a peak point is %d",findPeak(arr, n));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// A Java program to find a peak element
import java.util.*;
class GFG {
// Find the peak element in the array
static int findPeak(int arr[], int n)
{
// First or last element is peak element
if (n == 1)
return 0;
if (arr[0] >= arr[1])
return 0;
if (arr[n - 1] >= arr[n - 2])
return n - 1;
// Check for every other element
for (int i = 1; i < n - 1; i++) {
// Check if the neighbors are smaller
if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1])
return i;
}
return 0;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = arr.length;
System.out.print("Index of a peak point is " + findPeak(arr, n));
}
}
// This code is contributed by Aditya Kumar (adityakumar129)
Python3
# A Python3 program to find a peak element
# Find the peak element in the array
def findPeak(arr, n) :
# first or last element is peak element
if (n == 1) :
return 0
if (arr[0] >= arr[1]) :
return 0
if (arr[n - 1] >= arr[n - 2]) :
return n - 1
# check for every other element
for i in range(1, n - 1) :
# check if the neighbors are smaller
if (arr[i] >= arr[i - 1] and arr[i] >= arr[i + 1]) :
return i
# Driver code.
arr = [ 1, 3, 20, 4, 1, 0 ]
n = len(arr)
print("Index of a peak point is", findPeak(arr, n))
# This code is contributed by divyeshrabadiya07
C#
// A C# program to find a peak element
using System;
public class GFG{
// Find the peak element in the array
static int findPeak(int []arr, int n)
{
// First or last element is peak element
if (n == 1)
return 0;
if (arr[0] >= arr[1])
return 0;
if (arr[n - 1] >= arr[n - 2])
return n - 1;
// Check for every other element
for(int i = 1; i < n - 1; i++)
{
// Check if the neighbors are smaller
if (arr[i] >= arr[i - 1] &&
arr[i] >= arr[i + 1])
return i;
}
return 0;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 3, 20, 4, 1, 0 };
int n = arr.Length;
Console.Write("Index of a peak point is " +
findPeak(arr, n));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// A JavaScript program to find a peak element
// Find the peak element in the array
function findPeak(arr, n)
{
// first or last element is peak element
if (n == 1) return 0;
if (arr[0] >= arr[1]) return 0;
if (arr[n - 1] >= arr[n - 2]) return n - 1;
// check for every other element
for (var i = 1; i < n - 1; i++)
{
// check if the neighbors are smaller
if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1]) return i;
}
}
// Driver Code
var arr = [1, 3, 20, 4, 1, 0];
var n = arr.length;
document.write("Index of a peak point is " + findPeak(arr, n));
// This code is contributed by rdtank.
</script>
C++
// A C++ program to find a peak element
// using divide and conquer
#include <bits/stdc++.h>
using namespace std;
// A binary search based function
// that returns index of a peak element
int findPeakUtil(int arr[], int low,
int high, int n)
{
// Find index of middle element
// low + (high - low) / 2
int mid = low + (high - low) / 2;
// Compare middle element with its
// neighbours (if neighbours exist)
if ((mid == 0 || arr[mid - 1] <= arr[mid]) &&
(mid == n - 1 || arr[mid + 1] <= arr[mid]))
return mid;
// If middle element is not peak and its
// left neighbour is greater than it,
// then left half must have a peak element
else if (mid > 0 && arr[mid - 1] > arr[mid])
return findPeakUtil(arr, low, (mid - 1), n);
// If middle element is not peak and its
// right neighbour is greater than it,
// then right half must have a peak element
else
return findPeakUtil(
arr, (mid + 1), high, n);
}
// A wrapper over recursive function findPeakUtil()
int findPeak(int arr[], int n)
{
return findPeakUtil(arr, 0, n - 1, n);
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Index of a peak point is "
<< findPeak(arr, n);
return 0;
}
// This code is contributed by rajdeep999
C
// C program to find a peak
// element using divide and conquer
#include <stdio.h>
// A binary search based function that
// returns index of a peak element
int findPeakUtil(
int arr[], int low, int high, int n)
{
// Find index of middle element
// low + (high - low) / 2
int mid = low + (high - low) / 2;
// Compare middle element with
// its neighbours (if neighbours exist)
if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == n - 1 || arr[mid + 1] <= arr[mid]))
return mid;
// If middle element is not peak and
// its left neighbour is greater
// than it, then left half must have a peak element
else if (mid > 0 && arr[mid - 1] > arr[mid])
return findPeakUtil(arr, low, (mid - 1), n);
// If middle element is not peak and
// its right neighbour is greater
// than it, then right half must have a peak element
else
return findPeakUtil(arr, (mid + 1), high, n);
}
// A wrapper over recursive function findPeakUtil()
int findPeak(int arr[], int n)
{
return findPeakUtil(arr, 0, n - 1, n);
}
/* Driver program to check above functions */
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
printf(
"Index of a peak point is %d", findPeak(arr, n));
return 0;
}
Java
// A Java program to find a peak
// element using divide and conquer
import java.util.*;
import java.lang.*;
import java.io.*;
class PeakElement {
// A binary search based function
// that returns index of a peak element
static int findPeakUtil(
int arr[], int low, int high, int n)
{
// Find index of middle element
// low + (high - low) / 2
int mid = low + (high - low) / 2;
// Compare middle element with its
// neighbours (if neighbours exist)
if ((mid == 0 || arr[mid - 1] <= arr[mid])
&& (mid == n - 1 || arr[mid + 1] <= arr[mid]))
return mid;
// If middle element is not peak
// and its left neighbor is
// greater than it, then left half
// must have a peak element
else if (mid > 0 && arr[mid - 1] > arr[mid])
return findPeakUtil(arr, low, (mid - 1), n);
// If middle element is not peak
// and its right neighbor
// is greater than it, then right
// half must have a peak
// element
else
return findPeakUtil(
arr, (mid + 1), high, n);
}
// A wrapper over recursive function
// findPeakUtil()
static int findPeak(int arr[], int n)
{
return findPeakUtil(arr, 0, n - 1, n);
}
// Driver method
public static void main(String[] args)
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = arr.length;
System.out.println(
"Index of a peak point is " + findPeak(arr, n));
}
}
Python3
# A python3 program to find a peak
# element using divide and conquer
# A binary search based function
# that returns index of a peak element
def findPeakUtil(arr, low, high, n):
# Find index of middle element
# low + (high - low) / 2
mid = low + (high - low)/2
mid = int(mid)
# Compare middle element with its
# neighbours (if neighbours exist)
if ((mid == 0 or arr[mid - 1] <= arr[mid]) and
(mid == n - 1 or arr[mid + 1] <= arr[mid])):
return mid
# If middle element is not peak and
# its left neighbour is greater
# than it, then left half must
# have a peak element
elif (mid > 0 and arr[mid - 1] > arr[mid]):
return findPeakUtil(arr, low, (mid - 1), n)
# If middle element is not peak and
# its right neighbour is greater
# than it, then right half must
# have a peak element
else:
return findPeakUtil(arr, (mid + 1), high, n)
# A wrapper over recursive
# function findPeakUtil()
def findPeak(arr, n):
return findPeakUtil(arr, 0, n - 1, n)
# Driver code
arr = [1, 3, 20, 4, 1, 0]
n = len(arr)
print("Index of a peak point is", findPeak(arr, n))
# This code is contributed by
# Smitha Dinesh Semwal
C#
// A C# program to find
// a peak element
// using divide and conquer
using System;
class GFG {
// A binary search based
// function that returns
// index of a peak element
static int findPeakUtil(int[] arr, int low,
int high, int n)
{
// Find index of
// middle element mid = low + (high - low) / 2
int mid = low + (high - low) / 2;
// Compare middle element with
// its neighbours (if neighbours
// exist)
if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == n - 1 || arr[mid + 1] <= arr[mid]))
return mid;
// If middle element is not
// peak and its left neighbor
// is greater than it, then
// left half must have a
// peak element
else if (mid > 0 && arr[mid - 1] > arr[mid])
return findPeakUtil(arr, low,
(mid - 1), n);
// If middle element is not
// peak and its right neighbor
// is greater than it, then
// right half must have a peak
// element
else
return findPeakUtil(arr, (mid + 1),
high, n);
}
// A wrapper over recursive
// function findPeakUtil()
static int findPeak(int[] arr,
int n)
{
return findPeakUtil(arr, 0,
n - 1, n);
}
// Driver Code
static public void Main()
{
int[] arr = { 1, 3, 20,
4, 1, 0 };
int n = arr.Length;
Console.WriteLine("Index of a peak "
+ "point is " + findPeak(arr, n));
}
}
// This code is contributed by ajit
PHP
<?php
// A PHP program to find a
// peak element using
// divide and conquer
// A binary search based function
// that returns index of a peak
// element
function findPeakUtil($arr, $low,
$high, $n)
{
// Find index of middle element
$mid = $low + ($high - $low) / 2; // (low + high)/2
// Compare middle element with
// its neighbours (if neighbours exist)
if (($mid == 0 ||
$arr[$mid - 1] <= $arr[$mid]) &&
($mid == $n - 1 ||
$arr[$mid + 1] <= $arr[$mid]))
return $mid;
// If middle element is not peak
// and its left neighbour is greater
// than it, then left half must
// have a peak element
else if ($mid > 0 &&
$arr[$mid - 1] > $arr[$mid])
return findPeakUtil($arr, $low,
($mid - 1), $n);
// If middle element is not peak
// and its right neighbour is
// greater than it, then right
// half must have a peak element
else return(findPeakUtil($arr, ($mid + 1),
$high, $n));
}
// A wrapper over recursive
// function findPeakUtil()
function findPeak($arr, $n)
{
return floor(findPeakUtil($arr, 0,
$n - 1, $n));
}
// Driver Code
$arr = array(1, 3, 20, 4, 1, 0);
$n = sizeof($arr);
echo "Index of a peak point is ",
findPeak($arr, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// A Javascript program to find a peak element
// using divide and conquer
// A binary search based function
// that returns index of a peak element
function findPeakUtil(arr, low, high, n)
{
// Find index of middle element
// low + (high - low) / 2
var mid = low + parseInt((high - low) / 2);
// Compare middle element with its
// neighbours (if neighbours exist)
if ((mid == 0 || arr[mid - 1] <= arr[mid]) &&
(mid == n - 1 || arr[mid + 1] <= arr[mid]))
return mid;
// If middle element is not peak and its
// left neighbour is greater than it,
// then left half must have a peak element
else if (mid > 0 && arr[mid - 1] > arr[mid])
return findPeakUtil(arr, low, (mid - 1), n);
// If middle element is not peak and its
// right neighbour is greater than it,
// then right half must have a peak element
else
return findPeakUtil(
arr, (mid + 1), high, n);
}
// A wrapper over recursive function findPeakUtil()
function findPeak(arr, n)
{
return findPeakUtil(arr, 0, n - 1, n);
}
// Driver Code
var arr = [ 1, 3, 20, 4, 1, 0 ];
var n = arr.length;
document.write("Index of a peak point is "
+ findPeak(arr, n));
</script>
C++
// A C++ program to find a peak element
// using divide and conquer
#include <bits/stdc++.h>
using namespace std;
// A binary search based function
// that returns index of a peak element
int findPeak(int arr[], int n)
{
int l = 0;
int r = n-1;
int mid;
while (l <= r) {
// finding mid by binary right shifting.
mid = (l + r) >> 1;
// first case if mid is the answer
if ((mid == 0 || arr[mid - 1] <= arr[mid])
and (mid == n - 1 || arr[mid + 1] <= arr[mid]))
break;
// move the right pointer
if (mid > 0 and arr[mid - 1] > arr[mid])
r = mid - 1;
// move the left pointer
else
l = mid + 1;
}
return mid;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Index of a peak point is " << findPeak(arr, n);
return 0;
}
// This code is contributed by Rajdeep Mallick (rajdeep999)
C
// A C program to find a peak element using divide and
// conquer
#include <stdio.h>
// A binary search based function
// that returns index of a peak element
int findPeak(int arr[], int n)
{
int l = 0;
int r = n-1;
int mid;
while (l <= r) {
// finding mid by binary right shifting.
mid = (l + r) >> 1;
// first case if mid is the answer
if ((mid == 0 || arr[mid - 1] <= arr[mid])
&& (mid == n - 1 || arr[mid + 1] <= arr[mid]))
break;
// move the right pointer
if (mid > 0 && arr[mid - 1] > arr[mid])
r = mid - 1;
// move the left pointer
else
l = mid + 1;
}
return mid;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Index of a peak point is %d", findPeak(arr, n));
return 0;
}
// This code is contributed by Rajdeep Mallick (rajdeep999)
Java
// A Java program to find a peak element using divide and
// conquer
class GFG {
// A binary search based function that returns index of
// a peak element
static int findPeak(int arr[], int n)
{
int l = 0;
int r = n-1;
int mid = 0;
while (l <= r) {
// finding mid by binary right shifting.
mid = (l + r) >> 1;
// first case if mid is the answer
if ((mid == 0
|| arr[mid - 1] <= arr[mid])
&& (mid == n - 1
|| arr[mid + 1] <= arr[mid]))
break;
// move the right pointer
if (mid > 0 && arr[mid - 1] > arr[mid])
r = mid - 1;
// move the left pointer
else
l = mid + 1;
}
return mid;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 1, 3, 20, 4, 1, 0 };
int n = arr.length;
System.out.println("Index of a peak point is "
+ findPeak(arr, n));
}
}
// This code is contributed by Rajdeep Mallick (rajdeep999)
Python3
# A Python program to find a peak element
# using divide and conquer
# A binary search based function
# that returns index of a peak element
def findPeak(arr, n):
l = 0
r = n-1
while(l <= r):
# finding mid by binary right shifting.
mid = (l + r) >> 1
# first case if mid is the answer
if((mid == 0 or arr[mid - 1] <= arr[mid]) and (mid == n - 1 or arr[mid + 1] <= arr[mid])):
break
# move the right pointer
if(mid > 0 and arr[mid - 1] > arr[mid]):
r = mid - 1
# move the left pointer
else:
l = mid + 1
return mid
# Driver Code
arr = [1, 3, 20, 4, 1, 0]
n = len(arr)
print(f"Index of a peak point is {findPeak(arr, n)}")
# This code is contributed by Rajdeep Mallick (rajdeep999)
C#
// A C# program to find a peak element
// using divide and conquer
using System;
public class GFG {
// A binary search based function
// that returns index of a peak element
static int findPeak(int[] arr, int n)
{
int l = 0;
int r = n-1;
int mid = 0;
while (l <= r) {
// finding mid by binary right shifting.
mid = (l + r) >> 1;
// first case if mid is the answer
if ((mid == 0
|| arr[mid - 1] <= arr[mid]
&& (mid == n - 1
|| arr[mid + 1] <= arr[mid])))
break;
// move the right pointer
if (mid > 0 && arr[mid - 1] > arr[mid])
r = mid - 1;
// move the left pointer
else
l = mid + 1;
}
return mid;
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 1, 3, 20, 4, 1, 0 };
int n = arr.Length;
Console.WriteLine("Index of a peak point is "
+ findPeak(arr, n));
}
}
// This code is contributed by Rajdeep Mallick (rajdeep999)
Javascript
<script>
// A JavaScript program to find a peak element
// using divide and conquer
// A binary search based function
// that returns index of a peak element
function findPeakUtil(arr, low, high, n)
{
let l = low;
let r = high - 1;
let mid;
while(l <= r)
{
// finding the mid index by right shifting
mid = (l + r) >> 1;
// first case if mid is the answer
if((mid == 0 || arr[mid - 1] <= arr[mid]) &&
(mid == n - 1 || arr[mid + 1] <= arr[mid]))
break;
// change the right pointer to mid-1
if(mid > 0 && arr[mid - 1] > arr[mid])
r = mid - 1;
// change the left pointer to mid+1
else
l = mid + 1;
}
return mid;
}
// A wrapper over recursive function findPeakUtil()
function findPeak(arr,n)
{
return findPeakUtil(arr, 0, n, n);
}
// Driver Code
let arr = [ 1, 3, 20, 4, 1, 0 ];
let n = arr.length;
document.write("Index of a peak point is " +findPeak(arr, n));
// This code is contributed by Rajdeep Mallick (rajdeep999)
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA