Dada una array ordenada arr[] de tamaño N y una clave entera , la tarea es encontrar el índice en el que la clave está presente en la array. La array dada se obtuvo invirtiendo las subarreglas {arr[0], arr[R]} y {arr[R + 1], arr[N – 1]} en algún índice aleatorio R. Si la clave no está presente en el array, imprime -1 .
Ejemplos:
Entrada : arr[] = {4, 3, 2, 1, 8, 7, 6, 5}, clave = 2
Salida: 2Entrada: arr[] = {10, 8, 6, 5, 2, 1, 13, 12}, clave = 4
Salida: -1
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array y verificar si la clave está presente en la array o no. Si lo encuentra, imprima el índice. De lo contrario, imprima -1.
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es aplicar una búsqueda binaria modificada en la array para encontrar la clave . Siga los pasos a continuación para resolver este problema:
- Inicialice l como 0 y h como N – 1, para almacenar los índices de los elementos de contorno de un espacio de búsqueda para la búsqueda binaria .
- Iterar mientras l es menor o igual que h:
- Almacene el valor medio en una variable, mid como (l+h)/2 .
- Si arr[mid] es igual a key , imprima mid como la respuesta y regrese.
- Si arr[l] es mayor o igual que arr[mid] , esto significa que el índice aleatorio se encuentra en el lado derecho de mid .
- Si el valor de la clave está entre arr[mid] y arr[l] , actualice h a mid-1
- De lo contrario, actualice l a mid+1.
- De lo contrario, significa que el punto aleatorio se encuentra a la izquierda de mid .
- Si el valor de la clave está entre arr[h] y arr[mid], actualice l a mid+1.
- De lo contrario, actualice h a mid-1 .
- Finalmente, imprima -1 si no se encuentra la clave .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to search an element in a
// sorted array formed by reversing
// subarrays from a random index
int find(vector<int> arr, int N, int key)
{
// Set the boundaries
// for binary search
int l = 0;
int h = N - 1;
// Apply binary search
while (l <= h)
{
// Initialize the middle element
int mid = (l + h) / 2;
// If element found
if (arr[mid] == key)
return mid;
// Random point is on
// right side of mid
if (arr[l] >= arr[mid])
{
// From l to mid arr
// is reverse sorted
if (arr[l] >= key && key >= arr[mid])
h = mid - 1;
else
l = mid + 1;
}
// Random point is on
// the left side of mid
else
{
// From mid to h arr
// is reverse sorted
if (arr[mid] >= key && key >= arr[h])
l = mid + 1;
else
h = mid - 1;
}
}
// Return Not Found
return -1;
}
// Driver Code
int main()
{
// Given Input
vector<int> arr = { 10, 8, 6, 5, 2, 1, 13, 12 };
int N = arr.size();
int key = 8;
// Function Call
int ans = find(arr, N, key);
cout << ans;
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.util.*;
public class GFG {
// Function to search an element in a
// sorted array formed by reversing
// subarrays from a random index
public static int find(Vector<Integer> arr, int N, int key)
{
// Set the boundaries
// for binary search
int l = 0;
int h = N - 1;
// Apply binary search
while (l <= h)
{
// Initialize the middle element
int mid = (l + h) / 2;
// If element found
if (arr.get(mid) == key)
return mid;
// Random point is on
// right side of mid
if (arr.get(l) >= arr.get(mid))
{
// From l to mid arr
// is reverse sorted
if (arr.get(l) >= key && key >= arr.get(mid))
h = mid - 1;
else
l = mid + 1;
}
// Random point is on
// the left side of mid
else
{
// From mid to h arr
// is reverse sorted
if (arr.get(mid) >= key && key >= arr.get(h))
l = mid + 1;
else
h = mid - 1;
}
}
// Return Not Found
return -1;
}
// Drive Code
public static void main(String args[])
{
Vector<Integer> arr = new Vector <Integer>();
arr.add(10);
arr.add(8);
arr.add(6);
arr.add(5);
arr.add(2);
arr.add(1);
arr.add(13);
arr.add(12);
int N = arr.size();
int key = 8;
// Function Call
int ans = find(arr, N, key);
System.out.println( ans);
}
}
//This code is contributed by SoumikMondal
Python3
# Python program for the above approach # Function to search an element in a # sorted array formed by reversing # subarrays from a random index def find(arr, N, key): # Set the boundaries # for binary search l = 0 h = N-1 # Apply binary search while l <= h: # Initialize the middle element mid = (l+h)//2 # If element found if arr[mid] == key: return mid # Random point is on # right side of mid if arr[l] >= arr[mid]: # From l to mid arr # is reverse sorted if arr[l] >= key >= arr[mid]: h = mid-1 else: l = mid+1 # Random point is on # the left side of mid else: # From mid to h arr # is reverse sorted if arr[mid] >= key >= arr[h]: l = mid+1 else: h = mid-1 # Return Not Found return -1 # Driver Code if __name__ == "__main__": # Given Input arr = [10, 8, 6, 5, 2, 1, 13, 12] N = len(arr) key = 8 # Function Call ans = find(arr, N, key) print(ans)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to search an element in a
// sorted array formed by reversing
// subarrays from a random index
static int find(List<int> arr, int N, int key)
{
// Set the boundaries
// for binary search
int l = 0;
int h = N - 1;
// Apply binary search
while (l <= h)
{
// Initialize the middle element
int mid = (l + h) / 2;
// If element found
if (arr[mid] == key)
return mid;
// Random point is on
// right side of mid
if (arr[l] >= arr[mid])
{
// From l to mid arr
// is reverse sorted
if (arr[l] >= key && key >= arr[mid])
h = mid - 1;
else
l = mid + 1;
}
// Random point is on
// the left side of mid
else
{
// From mid to h arr
// is reverse sorted
if (arr[mid] >= key && key >= arr[h])
l = mid + 1;
else
h = mid - 1;
}
}
// Return Not Found
return -1;
}
// Driver Code
public static void Main()
{
// Given Input
List<int> arr = new List<int>(){ 10, 8, 6, 5,
2, 1, 13, 12 };
int N = arr.Count;
int key = 8;
// Function Call
int ans = find(arr, N, key);
Console.Write(ans);
}
}
// This code is contributed by ipg2016107
Javascript
<script>
// Javascript program for the above approach
// Function to search an element in a
// sorted array formed by reversing
// subarrays from a random index
function find(arr, N, key)
{
// Set the boundaries
// for binary search
let l = 0;
let h = N - 1;
// Apply binary search
while (l <= h)
{
// Initialize the middle element
let mid = Math.floor((l + h) / 2);
// If element found
if (arr[mid] == key)
return mid;
// Random point is on
// right side of mid
if (arr[l] >= arr[mid])
{
// From l to mid arr
// is reverse sorted
if (arr[l] >= key && key >= arr[mid])
h = mid - 1;
else
l = mid + 1;
}
// Random point is on
// the left side of mid
else
{
// From mid to h arr
// is reverse sorted
if (arr[mid] >= key && key >= arr[h])
l = mid + 1;
else
h = mid - 1;
}
}
// Return Not Found
return -1;
}
// Driver Code
// Given Input
let arr = [ 10, 8, 6, 5, 2, 1, 13, 12 ];
let N = arr.length;
let key = 8;
// Function Call
let ans = find(arr, N, key);
document.write(ans);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
1
Complejidad de tiempo: O(log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por harshitkap00r y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA