Dada una array ordenada arr[] que consta de N enteros distintos y un entero K , la tarea es encontrar el índice de K, si está presente en la array arr[] . De lo contrario, busque el índice donde se debe insertar K para mantener ordenada la array.
Ejemplos:
Entrada: arr[] = {1, 3, 5, 6}, K = 5
Salida: 2
Explicación: Dado que 5 se encuentra en el índice 2 como arr[2] = 5, la salida es 2.Entrada: arr[] = {1, 3, 5, 6}, K = 2
Salida: 1
Explicación: Dado que 2 no está presente en la array, se puede insertar en el índice 1 para ordenar la array.
Enfoque ingenuo: siga los pasos a continuación para resolver el problema:
- Iterar sobre cada elemento de la array arr[] y buscar el entero K.
- Si se encuentra que algún elemento de la array es igual a K , imprima el índice de K.
- De lo contrario, si se encuentra que algún elemento de la array es mayor que K , imprima ese índice como la posición de inserción de K . Si no se encuentra ningún elemento que exceda K , K debe insertarse después del último elemento de la array.
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 find insert position of K
int find_index(int arr[], int n, int K)
{
// Traverse the array
for (int i = 0; i < n; i++)
// If K is found
if (arr[i] == K)
return i;
// If current array element exceeds K
else if (arr[i] > K)
return i;
// If all elements are smaller than K
return n;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout << find_index(arr, n, K) << endl;
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program for the above approach
#include <stdio.h>
// Function to find insert position of K
int find_index(int arr[], int n, int K)
{
// Traverse the array
for (int i = 0; i < n; i++)
// If K is found
if (arr[i] == K)
return i;
// If current array element exceeds K
else if (arr[i] > K)
return i;
// If all elements are smaller than K
return n;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int K = 2;
printf("%d\n", find_index(arr, n, K));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find insert position of K
static int find_index(int[] arr, int n, int K)
{
// Traverse the array
for(int i = 0; i < n; i++)
// If K is found
if (arr[i] == K)
return i;
// If current array element
// exceeds K
else if (arr[i] > K)
return i;
// If all elements are smaller
// than K
return n;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 3, 5, 6 };
int n = arr.length;
int K = 2;
System.out.println(find_index(arr, n, K));
}
}
// This code is contributed by akhilsaini
Python3
# Python program for the above approach # Function to find insert position of K def find_index(arr, n, K): # Traverse the array for i in range(n): # If K is found if arr[i] == K: return i # If arr[i] exceeds K elif arr[i] > K: return i # If all array elements are smaller return n # Driver Code arr = [1, 3, 5, 6] n = len(arr) K = 2 print(find_index(arr, n, K))
C#
// C# program for the above approach
using System;
class GFG{
// Function to find insert position of K
static int find_index(int[] arr, int n, int K)
{
// Traverse the array
for(int i = 0; i < n; i++)
// If K is found
if (arr[i] == K)
return i;
// If current array element
// exceeds K
else if (arr[i] > K)
return i;
// If all elements are smaller
// than K
return n;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 3, 5, 6 };
int n = arr.Length;
int K = 2;
Console.WriteLine(find_index(arr, n, K));
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// Javascript program for the above approach
// Function to find insert position of K
function find_index(arr, n, K)
{
// Traverse the array
for(let i = 0; i < n; i++)
// If K is found
if (arr[i] == K)
return i;
// If current array element
// exceeds K
else if (arr[i] > K)
return i;
// If all elements are smaller
// than K
return n;
}
// Driver code
let arr = [ 1, 3, 5, 6 ];
let n = arr.length;
let K = 2;
document.write(find_index(arr, n, K));
// This code is contributed by splevel62
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la búsqueda binaria . Siga los pasos a continuación para resolver el problema:
- Establezca start y end como 0 y N – 1 , donde las variables start y end indican el límite inferior y superior del espacio de búsqueda, respectivamente.
- Calcula mid = (start + end) / 2 .
- Si se encuentra que arr[mid] es igual a K , imprima mid como la respuesta requerida.
- Si arr[mid] excede K , configure high = mid – 1 De lo contrario, configure low = mid + 1 .
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 find insert position of K
int find_index(int arr[], int n, int K)
{
// Lower and upper bounds
int start = 0;
int end = n - 1;
// Traverse the search space
while (start <= end) {
int mid = (start + end) / 2;
// If K is found
if (arr[mid] == K)
return mid;
else if (arr[mid] < K)
start = mid + 1;
else
end = mid - 1;
}
// Return insert position
return end + 1;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout << find_index(arr, n, K) << endl;
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program for the above approach
#include<stdio.h>
// Function to find insert position of K
int find_index(int arr[], int n, int K)
{
// Lower and upper bounds
int start = 0;
int end = n - 1;
// Traverse the search space
while (start <= end) {
int mid = (start + end) / 2;
// If K is found
if (arr[mid] == K)
return mid;
else if (arr[mid] < K)
start = mid + 1;
else
end = mid - 1;
}
// Return insert position
return end + 1;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
int K = 2;
printf("%d",find_index(arr, n, K));
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find insert position of K
static int find_index(int[] arr, int n, int K)
{
// Lower and upper bounds
int start = 0;
int end = n - 1;
// Traverse the search space
while (start <= end)
{
int mid = (start + end) / 2;
// If K is found
if (arr[mid] == K)
return mid;
else if (arr[mid] < K)
start = mid + 1;
else
end = mid - 1;
}
// Return insert position
return end + 1;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 3, 5, 6 };
int n = arr.length;
int K = 2;
System.out.println(find_index(arr, n, K));
}
}
// This code is contributed by akhilsaini
Python3
# Python program to implement # the above approach # Function to find insert position of K def find_index(arr, n, B): # Lower and upper bounds start = 0 end = n - 1 # Traverse the search space while start<= end: mid =(start + end)//2 if arr[mid] == K: return mid elif arr[mid] < K: start = mid + 1 else: end = mid-1 # Return the insert position return end + 1 # Driver Code arr = [1, 3, 5, 6] n = len(arr) K = 2 print(find_index(arr, n, K))
C#
// C# program for the above approach
using System;
class GFG{
// Function to find insert position of K
static int find_index(int[] arr, int n, int K)
{
// Lower and upper bounds
int start = 0;
int end = n - 1;
// Traverse the search space
while (start <= end)
{
int mid = (start + end) / 2;
// If K is found
if (arr[mid] == K)
return mid;
else if (arr[mid] < K)
start = mid + 1;
else
end = mid - 1;
}
// Return insert position
return end + 1;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 3, 5, 6 };
int n = arr.Length;
int K = 2;
Console.WriteLine(find_index(arr, n, K));
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// JavaScript program for the above approach
// Function to find insert position of K
function find_index(arr, n, K)
{
// Lower and upper bounds
let start = 0;
let end = n - 1;
// Traverse the search space
while (start <= end) {
let mid = Math.floor((start + end) / 2);
// If K is found
if (arr[mid] == K)
return mid;
else if (arr[mid] < K)
start = mid + 1;
else
end = mid - 1;
}
// Return insert position
return end + 1;
}
// Driver Code
let arr = [ 1, 3, 5, 6 ];
let n = arr.length;
let K = 2;
document.write(find_index(arr, n, K) + "<br>");
// This code is contributed by Surbhi Tyagi.
</script>
Producción:
1
Complejidad temporal: O(log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por deepanshu_rustagi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA