Dada una array arr[] que consta de N enteros, la tarea es encontrar el recuento máximo de enteros que se pueden buscar en binario en la array dada.
Ejemplos:
Entrada: arr[] = {1, 3, 2}
Salida: 2
Explicación: se puede encontrar arr[0], arr[1].Entrada: arr[] = {3, 2, 1, 10, 23, 22, 21}
Salida: 3
Explicación: arr[1], arr[3], arr[5] se pueden encontrar utilizando la búsqueda binaria independientemente de si el la array está ordenada o no.
Enfoque: el problema dado se puede resolver buscando cada elemento por separado en la array utilizando el enfoque de búsqueda binaria e incrementando el recuento de los enteros que existen en la array. Siga los pasos a continuación para resolver el problema:
- Haga una variable count = 0 , que almacenará el recuento de elementos que se pueden buscar de forma binaria.
- Para cada elemento, realice la búsqueda binaria en el rango [0, N) como:
- Inicialice la variable l como 0 y r como N-1 y realice la búsqueda binaria de arr[i] .
- Para cada iteración del ciclo while hasta que l sea menor que r, calcule el valor medio indicado por (l + r)/2 .
- Si arr[mid] es igual a arr[i] entonces incremente el conteo en 1 .
- Si arr[mid] es menor que arr[i], cambie l como mid + 1 .
- De lo contrario, cambie r como mid – 1 .
- La respuesta final se almacenará en la variable contar .
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 the total count of
// elements that are binary searchable
int totalBinarySearchable(vector<int> arr)
{
// Stores the count of element that
// are binary searchable
int count = 0;
int N = arr.size();
// For each element check if it can
// be found by doing a binary search
for (int i = 0; i < N; i++) {
// Binary search range
int l = 0, r = N - 1;
// Do a binary Search
while (l <= r) {
int mid = (l + r) / 2;
// Array element found
if (arr[mid] == arr[i]) {
count++;
break;
}
if (arr[mid] < arr[i]) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
}
// Return the total count
return count;
}
// Driver Code
int main()
{
vector<int> arr = { 3, 2, 1, 10,
23, 22, 21 };
cout << totalBinarySearchable(arr);
return 0;
}
Java
// Java code for the above approach
import java.io.*;
class GFG
{
// Function to find the total count of
// elements that are binary searchable
static int totalBinarySearchable(int[] arr)
{
// Stores the count of element that
// are binary searchable
int count = 0;
int N = arr.length;
// For each element check if it can
// be found by doing a binary search
for (int i = 0; i < N; i++) {
// Binary search range
int l = 0, r = N - 1;
// Do a binary Search
while (l <= r) {
int mid = (l + r) / 2;
// Array element found
if (arr[mid] == arr[i]) {
count++;
break;
}
if (arr[mid] < arr[i]) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
}
// Return the total count
return count;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 3, 2, 1, 10, 23, 22, 21 };
System.out.println(totalBinarySearchable(arr));
}
}
// This code is contributed by Potta Lokesh
Python3
# python program for the above approach # Function to find the total count of # elements that are binary searchable def totalBinarySearchable(arr): # Stores the count of element that # are binary searchable count = 0 N = len(arr) # For each element check if it can # be found by doing a binary search for i in range(0, N): # Binary search range l = 0 r = N - 1 # Do a binary Search while (l <= r): mid = (l + r) // 2 # Array element found if (arr[mid] == arr[i]): count += 1 break if (arr[mid] < arr[i]): l = mid + 1 else: r = mid - 1 # Return the total count return count # Driver Code if __name__ == "__main__": arr = [3, 2, 1, 10, 23, 22, 21] print(totalBinarySearchable(arr)) # This code is contributed by rakeshsahni
C#
// C# code for the above approach
using System;
public class GFG
{
// Function to find the total count of
// elements that are binary searchable
static int totalBinarySearchable(int[] arr)
{
// Stores the count of element that
// are binary searchable
int count = 0;
int N = arr.Length;
// For each element check if it can
// be found by doing a binary search
for (int i = 0; i < N; i++) {
// Binary search range
int l = 0, r = N - 1;
// Do a binary Search
while (l <= r) {
int mid = (l + r) / 2;
// Array element found
if (arr[mid] == arr[i]) {
count++;
break;
}
if (arr[mid] < arr[i]) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
}
// Return the total count
return count;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 3, 2, 1, 10, 23, 22, 21 };
Console.WriteLine(totalBinarySearchable(arr));
}
}
// This code is contributed by rrrtnx.
Javascript
<script>
// Javascript program for the above approach
// Function to find the total count of
// elements that are binary searchable
function totalBinarySearchable(arr)
{
// Stores the count of element that
// are binary searchable
let count = 0;
let N = arr.length;
// For each element check if it can
// be found by doing a binary search
for (let i = 0; i < N; i++)
{
// Binary search range
let l = 0,
r = N - 1;
// Do a binary Search
while (l <= r) {
let mid = Math.floor((l + r) / 2);
// Array element found
if (arr[mid] == arr[i]) {
count++;
break;
}
if (arr[mid] < arr[i]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
// Return the total count
return count;
}
// Driver Code
let arr = [3, 2, 1, 10, 23, 22, 21];
document.write(totalBinarySearchable(arr));
// This code is contributed by gfgking.
</script>
Producción:
3
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA