Dada una secuencia bitónica de n elementos distintos y un número entero x , la tarea es escribir un programa para encontrar el elemento x dado en la secuencia bitónica en tiempo O (log n) .
Una secuencia bitónica es una secuencia de números que primero es estrictamente creciente y luego después de un punto decreciente.
Ejemplos:
Entrada: arr[] = {-3, 9, 18, 20, 17, 5, 1}, clave = 20
Salida: Encontrado en el índice 3Entrada: arr[] = {5, 6, 7, 8, 9, 10, 3, 2, 1}, clave = 30 Salida
: No encontrado
Enfoque ingenuo: una solución simple es hacer una búsqueda lineal . La complejidad temporal de esta solución sería O(n).
Enfoque eficiente: una solución eficiente se basa en la búsqueda binaria .
- La idea es encontrar el punto bitónico ‘k’ que es el índice del elemento máximo de una secuencia dada.
- Si el elemento a buscar es mayor que el elemento máximo devuelve -1,
- de lo contrario, busque el elemento en ambas mitades .
A continuación se muestra el algoritmo paso a paso sobre cómo hacer esto.
- Encuentre el punto bitónico en la array dada, es decir, el elemento máximo en la array bitónica dada. Esto se puede hacer en tiempo log(n) modificando el algoritmo de búsqueda binaria. Puede consultar esta publicación sobre cómo hacer esto.
- Si el elemento a buscar es igual al elemento en el punto bitónico, imprima el índice del punto bitónico.
- Si el elemento a buscar es mayor que el elemento en un punto bitónico, entonces el elemento no existe en la array.
- Si el elemento a buscar es menor que el elemento en un punto bitónico, busque el elemento en ambas mitades de la array mediante la búsqueda binaria.
A continuación se muestra la implementación de la idea anterior:
C++
// C++ code to search key in bitonic array
#include <iostream>
using namespace std;
// Function for binary search in ascending part
int ascendingBinarySearch(int arr[], int low,
int high, int key)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
// Function for binary search in
// descending part of array
int descendingBinarySearch(int arr[], int low,
int high, int key)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] < key)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
// finding bitonic point
int findBitonicPoint(int arr[], int n,
int l, int r)
{
int mid;
int bitonicPoint = 0;
mid = (r + l) / 2;
if (arr[mid] > arr[mid - 1]
&& arr[mid] > arr[mid + 1])
{
return mid;
}
else if (arr[mid] > arr[mid - 1]
&& arr[mid] < arr[mid + 1])
{
bitonicPoint = findBitonicPoint(arr, n, mid, r);
}
else if (arr[mid] < arr[mid - 1]
&& arr[mid] > arr[mid + 1])
{
bitonicPoint = findBitonicPoint(arr, n, l, mid);
}
return bitonicPoint;
}
// Function to search key in
// bitonic array
int searchBitonic(int arr[], int n,
int key, int index)
{
if (key > arr[index])
return -1;
else if (key == arr[index])
return index;
else {
int temp
= ascendingBinarySearch(arr,
0, index - 1,
key);
if (temp != -1) {
return temp;
}
// Search in right of k
return descendingBinarySearch(arr,
index + 1,
n - 1,
key);
}
}
// Driver code
int main()
{
int arr[] = { -8, 1, 2, 3, 4, 5, -2, -3 };
int key = 1;
int n, l, r;
n = sizeof(arr) / sizeof(arr[0]);
l = 0;
r = n - 1;
int index;
// Function call
index = findBitonicPoint(arr, n, l, r);
int x = searchBitonic(arr, n, key, index);
if (x == -1)
cout << "Element Not Found" << endl;
else
cout << "Element Found at index " << x << endl;
return 0;
}
Java
// Java code to search key in bitonic array
public class GFG {
// Function for binary search
// in ascending part
static int ascendingBinarySearch(int arr[],
int low,
int high,
int key)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (arr[mid] == key)
{
return mid;
}
if (arr[mid] > key)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1;
}
// Function for binary search in
// descending part of array
static int descendingBinarySearch(int arr[],
int low,
int high,
int key)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (arr[mid] == key)
{
return mid;
}
if (arr[mid] < key)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1;
}
// finding bitonic point
static int findBitonicPoint(int arr[],
int n,
int l,
int r)
{
int mid;
int bitonicPoint = 0;
mid = (r + l) / 2;
if (arr[mid] > arr[mid - 1]
&& arr[mid] > arr[mid + 1])
{
return mid;
}
else {
if (arr[mid] > arr[mid - 1]
&& arr[mid] < arr[mid + 1])
{
bitonicPoint = findBitonicPoint(arr, n, mid, r);
}
else {
if (arr[mid] < arr[mid - 1]
&& arr[mid] > arr[mid + 1])
{
bitonicPoint = findBitonicPoint(arr, n, l, mid);
}
}
}
return bitonicPoint;
}
// Function to search key in bitonic array
static int searchBitonic(int arr[], int n,
int key, int index)
{
if (key > arr[index])
{
return -1;
}
else if (key == arr[index])
{
return index;
}
else {
int temp = ascendingBinarySearch(
arr, 0, index - 1, key);
if (temp != -1)
{
return temp;
}
// Search in right of k
return descendingBinarySearch(arr, index + 1,
n - 1, key);
}
}
// Driver code
public static void main(String args[])
{
int arr[] = { -8, 1, 2, 3, 4, 5, -2, -3 };
int key = 5;
int n, l, r;
n = arr.length;
l = 0;
r = n - 1;
int index;
index = findBitonicPoint(arr, n, l, r);
int x = searchBitonic(arr, n, key, index);
if (x == -1) {
System.out.println("Element Not Found");
}
else {
System.out.println("Element Found at index "
+ x);
}
}
}
/*This code is contributed by 29AjayKumar*/
Python3
# Python code to search key in bitonic array
# Function for binary search in ascending part
def ascendingBinarySearch(arr, low, high, key):
while low <= high:
mid = low + (high - low) // 2
if arr[mid] == key:
return mid
if arr[mid] > key:
high = mid - 1
else:
low = mid + 1
return -1
# Function for binary search in descending part of array
def descendingBinarySearch(arr, low, high, key):
while low <= high:
mid = low + (high - low) // 2
if arr[mid] == key:
return mid
if arr[mid] < key:
high = mid - 1
else:
low = mid + 1
return -1
# Find bitonic point
def findBitonicPoint(arr, n, l, r):
bitonicPoint = 0
mid = (r + l) // 2
if arr[mid] > arr[mid-1] and arr[mid] > arr[mid+1]:
return mid
elif arr[mid] > arr[mid-1] and arr[mid] < arr[mid+1]:
bitonicPoint = findBitonicPoint(arr, n, mid, r)
else:
bitonicPoint = finsBitonicPoint(arr, n, l, mid)
return bitonicPoint
# Function to search key in bitonic array
def searchBitonic(arr, n, key, index):
if key > arr[index]:
return -1
elif key == arr[index]:
return index
else:
temp = ascendingBinarySearch(arr, 0, index-1, key)
if temp != -1:
return temp
# search in right of k
return descendingBinarySearch(arr, index+1, n-1, key)
# Driver code
def main():
arr = [-8, 1, 2, 3, 4, 5, -2, -3]
key = 1
n = len(arr)
l = 0
r = n - 1
# Function call
index = findBitonicPoint(arr, n, l, r)
x = searchBitonic(arr, n, key, index)
if x == -1:
print("Element Not Found")
else:
print("Element Found at index", x)
main()
# This code is contributed by stutipathak31jan
C#
// C# code to search key in bitonic array
using System;
class GFG {
// Function for binary search in ascending part
static int ascendingBinarySearch(int[] arr, int low,
int high, int key)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (arr[mid] == key)
{
return mid;
}
if (arr[mid] > key)
{
high = mid - 1;
}
else {
low = mid + 1;
}
}
return -1;
}
// Function for binary search in descending part of
// array
static int descendingBinarySearch(int[] arr, int low,
int high, int key)
{
while (low <= high)
{
int mid = low + (high - low) / 2;
if (arr[mid] == key)
{
return mid;
}
if (arr[mid] < key)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1;
}
// finding bitonic point
static int findBitonicPoint(int[] arr, int n, int l,
int r)
{
int mid;
int bitonicPoint = 0;
mid = (r + l) / 2;
if (arr[mid] > arr[mid - 1]
&& arr[mid] > arr[mid + 1])
{
return mid;
}
else
{
if (arr[mid] > arr[mid - 1]
&& arr[mid] < arr[mid + 1]) {
bitonicPoint = findBitonicPoint(arr, n, mid, r);
}
else
{
if (arr[mid] < arr[mid - 1]
&& arr[mid] > arr[mid + 1]) {
bitonicPoint = findBitonicPoint(arr, n, l, mid);
}
}
}
return bitonicPoint;
}
// Function to search key in bitonic array
static int searchBitonic(int[] arr, int n, int key,
int index)
{
if (key > arr[index])
{
return -1;
}
else if (key == arr[index])
{
return index;
}
else {
int temp = ascendingBinarySearch(
arr, 0, index - 1, key);
if (temp != -1) {
return temp;
}
// Search in right of k
return descendingBinarySearch(arr, index + 1,
n - 1, key);
}
}
// Driver Code
static public void Main()
{
int[] arr = { -8, 1, 2, 3, 4, 5, -2, -3 };
int key = 1;
int n, l, r;
n = arr.Length;
l = 0;
r = n - 1;
int index;
index = findBitonicPoint(arr, n, l, r);
int x = searchBitonic(arr, n, key, index);
if (x == -1) {
Console.WriteLine("Element Not Found");
}
else {
Console.WriteLine("Element Found at index "
+ x);
}
}
}
// This code is contributed by ajit
Javascript
<script>
// JavaScript code to search key in bitonic array
// Function for binary search in ascending part
function ascendingBinarySearch(arr, low, high, key) {
while (low <= high) {
let mid = Math.floor(low + (high - low) / 2);
if (arr[mid] == key)
return mid;
if (arr[mid] > key)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
// Function for binary search in
// descending part of array
function descendingBinarySearch(arr, low, high, key) {
while (low <= high) {
let mid = Math.floor(low + (high - low) / 2);
if (arr[mid] == key)
return mid;
if (arr[mid] < key)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
// finding bitonic point
function findBitonicPoint(arr, n, l, r) {
let mid;
let bitonicPoint = 0;
mid = Math.floor((r + l) / 2);
if (arr[mid] > arr[mid - 1]
&& arr[mid] > arr[mid + 1]) {
return mid;
}
else if (arr[mid] > arr[mid - 1]
&& arr[mid] < arr[mid + 1]) {
bitonicPoint = findBitonicPoint(arr, n, mid, r);
}
else if (arr[mid] < arr[mid - 1]
&& arr[mid] > arr[mid + 1]) {
bitonicPoint = findBitonicPoint(arr, n, l, mid);
}
return bitonicPoint;
}
// Function to search key in
// bitonic array
function searchBitonic(arr, n, key, index) {
if (key > arr[index])
return -1;
else if (key == arr[index])
return index;
else {
let temp
= ascendingBinarySearch(arr,
0, index - 1,
key);
if (temp != -1) {
return temp;
}
// Search in right of k
return descendingBinarySearch(arr,
index + 1,
n - 1,
key);
}
}
// Driver code
let arr = [-8, 1, 2, 3, 4, 5, -2, -3];
let key = 1;
let n, l, r;
n = arr.length;
l = 0;
r = n - 1;
let index;
// Function call
index = findBitonicPoint(arr, n, l, r);
let x = searchBitonic(arr, n, key, index);
if (x == -1)
document.write("Element Not Found" + "<br>");
else
document.write("Element Found at index " + x + "<br>");
</script>
Producción
Element Found at index 1
Complejidad temporal: O(log n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Vaishali Goyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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