Dada una array de N rangos ordenados y un número K . La tarea es encontrar el índice del rango en el que se encuentra K. Si K no se encuentra en ninguno de los rangos dados, imprima -1 .
Nota: Ninguno de los rangos dados coincide.
Ejemplos:
Entrada: arr[] = { { 1, 3 }, { 4, 7 }, { 8, 11 } }, K = 6
Salida: 1
6 se encuentra en el rango {4, 7} con índice = 1
Entrada: arr[ ] = { { 1, 3 }, { 4, 7 }, { 9, 11 } }, K = 8
Salida: -1
Enfoque ingenuo: se pueden seguir los siguientes pasos para resolver el problema anterior.
- Atraviesa todos los rangos.
- Compruebe si la condición K >= arr[i].primero && K <= arr[i].segundo se cumple en alguna de las iteraciones.
- Si el número K no se encuentra en ninguno de los rangos dados, imprima -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the index of the range
// in which K lies and uses linear search
int findNumber(pair<int, int> a[], int n, int K)
{
// Iterate and find the element
for (int i = 0; i < n; i++) {
// If K lies in the current range
if (K >= a[i].first && K <= a[i].second)
return i;
}
// K doesn't lie in any of the given ranges
return -1;
}
// Driver code
int main()
{
pair<int, int> a[] = { { 1, 3 }, { 4, 7 }, { 8, 11 } };
int n = sizeof(a) / sizeof(a[0]);
int k = 6;
int index = findNumber(a, n, k);
if (index != -1)
cout << index;
else
cout << -1;
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to return the index
// of the range in which K lies
// and uses linear search
static int findNumber(pair a[],
int n, int K)
{
// Iterate and find the element
for (int i = 0; i < n; i++)
{
// If K lies in the current range
if (K >= a[i].first &&
K <= a[i].second)
return i;
}
// K doesn't lie in any
// of the given ranges
return -1;
}
// Driver code
public static void main(String[] args)
{
pair a[] = {new pair(1, 3 ),
new pair(4, 7 ),
new pair(8, 11 )};
int n = a.length;
int k = 6;
int index = findNumber(a, n, k);
if (index != -1)
System.out.println(index);
else
System.out.println(-1);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python 3 implementation of the approach # Function to return the index of the range # in which K lies and uses linear search def findNumber(a, n, K): # Iterate and find the element for i in range(0, n, 1): # If K lies in the current range if (K >= a[i][0] and K <= a[i][1]): return i # K doesn't lie in any of the # given ranges return -1 # Driver code if __name__ == '__main__': a = [[1, 3], [4, 7], [8, 11]] n = len(a) k = 6 index = findNumber(a, n, k) if (index != -1): print(index, end = "") else: print(-1, end = "") # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to return the index
// of the range in which K lies
// and uses linear search
static int findNumber(pair []a,
int n, int K)
{
// Iterate and find the element
for (int i = 0; i < n; i++)
{
// If K lies in the current range
if (K >= a[i].first &&
K <= a[i].second)
return i;
}
// K doesn't lie in any
// of the given ranges
return -1;
}
// Driver code
public static void Main(String[] args)
{
pair []a = {new pair(1, 3 ),
new pair(4, 7 ),
new pair(8, 11 )};
int n = a.Length;
int k = 6;
int index = findNumber(a, n, k);
if (index != -1)
Console.WriteLine(index);
else
Console.WriteLine(-1);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the index of the range
// in which K lies and uses linear search
function findNumber(a, n, K)
{
// Iterate and find the element
for (var i = 0; i < n; i++) {
// If K lies in the current range
if (K >= a[i][0] && K <= a[i][1])
return i;
}
// K doesn't lie in any of the given ranges
return -1;
}
// Driver code
var a = [ [ 1, 3 ], [ 4, 7 ], [ 8, 11 ] ];
var n = a.length;
var k = 6;
var index = findNumber(a, n, k);
if (index != -1)
document.write( index);
else
document.write( -1);
</script>
Producción:
1
Complejidad de tiempo: O (N), ya que estamos usando un ciclo para atravesar N veces para verificar si el número se encuentra en el rango dado. Donde N es el número de pares en el arreglo.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Enfoque eficiente: la búsqueda binaria se puede utilizar para encontrar el elemento en O (log N).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the index of the range
// in which K lies and uses binary search
int findNumber(pair<int, int> a[], int n, int K)
{
int low = 0, high = n - 1;
// Binary search
while (low <= high) {
// Find the mid element
int mid = (low + high) >> 1;
// If element is found
if (K >= a[mid].first && K <= a[mid].second)
return mid;
// Check in first half
else if (K < a[mid].first)
high = mid - 1;
// Check in second half
else
low = mid + 1;
}
// Not found
return -1;
}
// Driver code
int main()
{
pair<int, int> a[] = { { 1, 3 }, { 4, 7 }, { 8, 11 } };
int n = sizeof(a) / sizeof(a[0]);
int k = 6;
int index = findNumber(a, n, k);
if (index != -1)
cout << index;
else
cout << -1;
return 0;
}
Java
// Java implementation of the approach
class GFG
{
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to return the index of the range
// in which K lies and uses binary search
static int findNumber(pair a[], int n, int K)
{
int low = 0, high = n - 1;
// Binary search
while (low <= high)
{
// Find the mid element
int mid = (low + high) >> 1;
// If element is found
if (K >= a[mid].first &&
K <= a[mid].second)
return mid;
// Check in first half
else if (K < a[mid].first)
high = mid - 1;
// Check in second half
else
low = mid + 1;
}
// Not found
return -1;
}
// Driver code
public static void main(String[] args)
{
pair a[] = { new pair(1, 3),
new pair(4, 7),
new pair(8, 11) };
int n = a.length;
int k = 6;
int index = findNumber(a, n, k);
if (index != -1)
System.out.println(index);
else
System.out.println(-1);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of the approach # Function to return the index of the range # in which K lies and uses binary search def findNumber(a, n, K): low = 0 high = n - 1 # Binary search while (low <= high): # Find the mid element mid = (low + high) >> 1 # If element is found if (K >= a[mid][0] and K <= a[mid][1]): return mid # Check in first half elif (K < a[mid][0]): high = mid - 1 # Check in second half else: low = mid + 1 # Not found return -1 # Driver code a= [ [ 1, 3 ], [ 4, 7 ], [ 8, 11 ] ] n = len(a) k = 6 index = findNumber(a, n, k) if (index != -1): print(index) else: print(-1) # This code is contributed by mohit kumar
C#
// C# implementation of the above approach
using System;
class GFG
{
public class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to return the index of the range
// in which K lies and uses binary search
static int findNumber(pair []a, int n, int K)
{
int low = 0, high = n - 1;
// Binary search
while (low <= high)
{
// Find the mid element
int mid = (low + high) >> 1;
// If element is found
if (K >= a[mid].first &&
K <= a[mid].second)
return mid;
// Check in first half
else if (K < a[mid].first)
high = mid - 1;
// Check in second half
else
low = mid + 1;
}
// Not found
return -1;
}
// Driver code
public static void Main(String[] args)
{
pair []a = {new pair(1, 3),
new pair(4, 7),
new pair(8, 11)};
int n = a.Length;
int k = 6;
int index = findNumber(a, n, k);
if (index != -1)
Console.WriteLine(index);
else
Console.WriteLine(-1);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
class pair {
constructor(first , second) {
this.first = first;
this.second = second;
}
}
// Function to return the index of the range
// in which K lies and uses binary search
function findNumber( a , n , K) {
var low = 0, high = n - 1;
// Binary search
while (low <= high) {
// Find the mid element
var mid = (low + high) >> 1;
// If element is found
if (K >= a[mid].first && K <= a[mid].second)
return mid;
// Check in first half
else if (K < a[mid].first)
high = mid - 1;
// Check in second half
else
low = mid + 1;
}
// Not found
return -1;
}
// Driver code
var a = [ new pair(1, 3), new pair(4, 7),
new pair(8, 11) ];
var n = a.length;
var k = 6;
var index = findNumber(a, n, k);
if (index != -1)
document.write(index);
else
document.write(-1);
// This code contributed by gauravrajput1
</script>
Producción:
1
Complejidad de tiempo: O (log N), como estamos usando búsqueda binaria, en cada recorrido dividimos la array en dos mitades y elegimos una de ellas para buscar más adentro. Entonces, el tiempo efectivo es 1+1/2+1/4 +….+1/2^N que es equivalente a logN. Donde N es el número de pares en el arreglo.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.