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>
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