Dada una array arr[] ordenada en orden decreciente y un número entero X , la tarea es verificar si X está presente en la array dada o no . Si X está presente en la array, imprima su índice ( indexación basada en 0 ). De lo contrario, imprima -1 .
Ejemplos:
Entrada: arr[] = {5, 4, 3, 2, 1}, X = 4
Salida: 1
Explicación: El elemento X (= 4) está presente en el índice 1.
Por lo tanto, la salida requerida es 1.Entrada: arr[] = {10, 8, 2, -9}, X = 5
Salida: -1
Explicación: El elemento X (= 5) no está presente en la array.
Por lo tanto, la salida requerida es -1.
Enfoque ingenuo: el enfoque más simple para resolver el problema es recorrer la array y, para cada elemento, verificar si es igual a X o no. Si se encuentra algún elemento que satisfaga esa condición, imprima el índice de ese elemento. De lo contrario, imprima -1 .
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: para resolver el problema, la idea es utilizar la búsqueda binaria basada en el enfoque discutido en el artículo sobre la búsqueda de un elemento en una array ordenada . Siga los pasos a continuación para resolver el problema:
- Compara X con el elemento del medio.
- Si X coincide con el elemento central ( arr[mid] ), devuelve el índice mid .
- Si se encuentra que X es mayor que arr[mid] , entonces X solo puede estar en el subarreglo [mid + 1, end] . Entonces busque X en el subarreglo {arr[mid + 1], .., arr[end]} .
- De lo contrario, busque en el subarreglo {arr[start], …., arr[mid]}
A continuación se muestra la implementación del enfoque anterior:
C
// C program for the above approach
#include <stdio.h>
// Function to search if element X
// is present in reverse sorted array
int binarySearch(int arr[], int N, int X)
{
// Store the first index of the
// subarray in which X lies
int start = 0;
// Store the last index of the
// subarray in which X lies
int end = N;
while (start <= end) {
// Store the middle index
// of the subarray
int mid = start
+ (end - start) / 2;
// Check if value at middle index
// of the subarray equal to X
if (X == arr[mid]) {
// Element is found
return mid;
}
// If X is smaller than the value
// at middle index of the subarray
else if (X < arr[mid]) {
// Search in right
// half of subarray
start = mid + 1;
}
else {
// Search in left
// half of subarray
end = mid - 1;
}
}
// If X not found
return -1;
}
// Driver Code
int main()
{
int arr[] = { 5, 4, 3, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
int X = 4;
int res = binarySearch(arr, N, X);
printf(" %d " , res);
return 0;
}
//This code is contributed by Pradeep Mondal P
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to search if element X
// is present in reverse sorted array
int binarySearch(int arr[], int N, int X)
{
// Store the first index of the
// subarray in which X lies
int start = 0;
// Store the last index of the
// subarray in which X lies
int end = N;
while (start <= end) {
// Store the middle index
// of the subarray
int mid = start
+ (end - start) / 2;
// Check if value at middle index
// of the subarray equal to X
if (X == arr[mid]) {
// Element is found
return mid;
}
// If X is smaller than the value
// at middle index of the subarray
else if (X < arr[mid]) {
// Search in right
// half of subarray
start = mid + 1;
}
else {
// Search in left
// half of subarray
end = mid - 1;
}
}
// If X not found
return -1;
}
// Driver Code
int main()
{
int arr[] = { 5, 4, 3, 2, 1 };
int N = sizeof(arr) / sizeof(arr[0]);
int X = 5;
cout << binarySearch(arr, N, X);
return 0;
}
Java
// Java Program to implement
// the above approach
class GFG {
// Function to search if element X
// is present in reverse sorted array
static int binarySearch(int arr[],
int N, int X)
{
// Store the first index of the
// subarray in which X lies
int start = 0;
// Store the last index of the
// subarray in which X lies
int end = N;
while (start <= end) {
// Store the middle index
// of the subarray
int mid = start
+ (end - start) / 2;
// Check if value at middle index
// of the subarray equal to X
if (X == arr[mid]) {
// Element is found
return mid;
}
// If X is smaller than the value
// at middle index of the subarray
else if (X < arr[mid]) {
// Search in right
// half of subarray
start = mid + 1;
}
else {
// Search in left
// half of subarray
end = mid - 1;
}
}
// If X not found
return -1;
}
public static void main(String[] args)
{
int arr[] = { 5, 4, 3, 2, 1 };
int N = arr.length;
int X = 5;
System.out.println(
binarySearch(arr, N, X));
}
}
Python3
# Python3 program to implement # the above approach # Function to search if element X # is present in reverse sorted array def binarySearch(arr, N, X): # Store the first index of the # subarray in which X lies start = 0 # Store the last index of the # subarray in which X lies end = N while (start <= end): # Store the middle index # of the subarray mid = start + (end - start) // 2 # Check if value at middle index # of the subarray equal to X if (X == arr[mid]): # Element is found return mid # If X is smaller than the value # at middle index of the subarray elif (X < arr[mid]): # Search in right # half of subarray start = mid + 1 else: # Search in left # half of subarray end = mid - 1 # If X not found return -1 # Driver Code if __name__ == '__main__': arr = [ 5, 4, 3, 2, 1 ] N = len(arr) X = 5 print(binarySearch(arr, N, X)) # This code is contributed by mohit kumar 29
C#
// C# Program to implement
// the above approach
using System;
class GFG{
// Function to search if element X
// is present in reverse sorted array
static int binarySearch(int []arr,
int N, int X)
{
// Store the first index of the
// subarray in which X lies
int start = 0;
// Store the last index of the
// subarray in which X lies
int end = N;
while (start <= end)
{
// Store the middle index
// of the subarray
int mid = start +
(end - start) / 2;
// Check if value at middle index
// of the subarray equal to X
if (X == arr[mid])
{
// Element is found
return mid;
}
// If X is smaller than the value
// at middle index of the subarray
else if (X < arr[mid])
{
// Search in right
// half of subarray
start = mid + 1;
}
else
{
// Search in left
// half of subarray
end = mid - 1;
}
}
// If X not found
return -1;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {5, 4, 3, 2, 1};
int N = arr.Length;
int X = 5;
Console.WriteLine(binarySearch(arr, N, X));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to search if element X
// is present in reverse sorted array
function binarySearch(arr, N, X)
{
// Store the first index of the
// subarray in which X lies
let start = 0;
// Store the last index of the
// subarray in which X lies
let end = N;
while (start <= end) {
// Store the middle index
// of the subarray
let mid = Math.floor(start
+ (end - start) / 2);
// Check if value at middle index
// of the subarray equal to X
if (X == arr[mid]) {
// Element is found
return mid;
}
// If X is smaller than the value
// at middle index of the subarray
else if (X < arr[mid]) {
// Search in right
// half of subarray
start = mid + 1;
}
else {
// Search in left
// half of subarray
end = mid - 1;
}
}
// If X not found
return -1;
}
// Driver Code
let arr = [ 5, 4, 3, 2, 1 ];
let N = arr.length;
let X = 5;
document.write(binarySearch(arr, N, X));
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
1
Complejidad de tiempo: O(log 2 N)
Espacio auxiliar: O(1)