Dada una función ‘int f(unsigned int x)’ que toma un entero no negativo ‘x’ como entrada y devuelve un entero como salida. La función es monótonamente creciente con respecto al valor de x, es decir, el valor de f(x+1) es mayor que f(x) para cada entrada x. Encuentre el valor ‘n’ donde f() se vuelve positivo por primera vez. Dado que f() es monótonamente creciente, los valores de f(n+1), f(n+2),… deben ser positivos y los valores de f(n-2), f(n-3),… deben ser negativos.
Encuentre n en el tiempo O (logn), puede suponer que f (x) se puede evaluar en el tiempo O (1) para cualquier entrada x.
Una solución sencilla es partir de i igual a 0 y calcular uno a uno el valor de f(i) para 1, 2, 3, 4…etc hasta encontrar una f(i) positiva. Esto funciona pero toma tiempo O(n).
¿Podemos aplicar la búsqueda binaria para encontrar n en el tiempo O (Logn)? No podemos aplicar directamente la búsqueda binaria ya que no tenemos un límite superior o un índice alto. La idea es duplicar repetidamente hasta que encontremos un valor positivo, es decir, verificar los valores de f() para los siguientes valores hasta que f(i) se vuelva positivo.
f(0) f(1) f(2) f(4) f(8) f(16) f(32) .... .... f(high) Let 'high' be the value of i when f() becomes positive for first time.
¿Podemos aplicar la búsqueda binaria para encontrar n después de encontrar ‘alto’? Podemos aplicar la búsqueda binaria ahora, podemos usar ‘alto/2’ como índice bajo y ‘alto’ como índice alto en la búsqueda binaria. El resultado n debe estar entre ‘alto/2’ y ‘alto’.
El número de pasos para encontrar ‘alto’ es O (Log). Entonces podemos encontrar ‘alto’ en el tiempo O (Log). ¿Qué pasa con el tiempo que tarda Binary Search entre high/2 y high? El valor de ‘alto’ debe ser inferior a 2*n. El número de elementos entre high/2 y high debe ser O(n). Por lo tanto, la complejidad temporal de la búsqueda binaria es O(Iniciar sesión) y la complejidad temporal general es 2*O(Iniciar sesión), que es O(Iniciar sesión).
C++
// C++ code for binary search
#include<bits/stdc++.h>
using namespace std;
int binarySearch(int low, int high); // prototype
// Let's take an example function
// as f(x) = x^2 - 10*x - 20 Note that
// f(x) can be any monotonically increasing function
int f(int x) { return (x*x - 10*x - 20); }
// Returns the value x where above
// function f() becomes positive
// first time.
int findFirstPositive()
{
// When first value itself is positive
if (f(0) > 0)
return 0;
// Find 'high' for binary search by repeated doubling
int i = 1;
while (f(i) <= 0)
i = i*2;
// Call binary search
return binarySearch(i/2, i);
}
// Searches first positive value
// of f(i) where low <= i <= high
int binarySearch(int low, int high)
{
if (high >= low)
{
int mid = low + (high - low)/2; /* mid = (low + high)/2 */
// If f(mid) is greater than 0 and
// one of the following two
// conditions is true:
// a) mid is equal to low
// b) f(mid-1) is negative
if (f(mid) > 0 && (mid == low || f(mid-1) <= 0))
return mid;
// If f(mid) is smaller than or equal to 0
if (f(mid) <= 0)
return binarySearch((mid + 1), high);
else // f(mid) > 0
return binarySearch(low, (mid -1));
}
/* Return -1 if there is no
positive value in given range */
return -1;
}
/* Driver code */
int main()
{
cout<<"The value n where f() becomes" <<
"positive first is "<< findFirstPositive();
return 0;
}
// This code is contributed by rathbhupendra
C
#include <stdio.h>
int binarySearch(int low, int high); // prototype
// Let's take an example function as f(x) = x^2 - 10*x - 20
// Note that f(x) can be any monotonically increasing function
int f(int x) { return (x*x - 10*x - 20); }
// Returns the value x where above function f() becomes positive
// first time.
int findFirstPositive()
{
// When first value itself is positive
if (f(0) > 0)
return 0;
// Find 'high' for binary search by repeated doubling
int i = 1;
while (f(i) <= 0)
i = i*2;
// Call binary search
return binarySearch(i/2, i);
}
// Searches first positive value of f(i) where low <= i <= high
int binarySearch(int low, int high)
{
if (high >= low)
{
int mid = low + (high - low)/2; /* mid = (low + high)/2 */
// If f(mid) is greater than 0 and one of the following two
// conditions is true:
// a) mid is equal to low
// b) f(mid-1) is negative
if (f(mid) > 0 && (mid == low || f(mid-1) <= 0))
return mid;
// If f(mid) is smaller than or equal to 0
if (f(mid) <= 0)
return binarySearch((mid + 1), high);
else // f(mid) > 0
return binarySearch(low, (mid -1));
}
/* Return -1 if there is no positive value in given range */
return -1;
}
/* Driver program to check above functions */
int main()
{
printf("The value n where f() becomes positive first is %d",
findFirstPositive());
return 0;
}
Java
// Java program for Binary Search
import java.util.*;
class Binary
{
public static int f(int x)
{ return (x*x - 10*x - 20); }
// Returns the value x where above
// function f() becomes positive
// first time.
public static int findFirstPositive()
{
// When first value itself is positive
if (f(0) > 0)
return 0;
// Find 'high' for binary search
// by repeated doubling
int i = 1;
while (f(i) <= 0)
i = i * 2;
// Call binary search
return binarySearch(i / 2, i);
}
// Searches first positive value of
// f(i) where low <= i <= high
public static int binarySearch(int low, int high)
{
if (high >= low)
{
/* mid = (low + high)/2 */
int mid = low + (high - low)/2;
// If f(mid) is greater than 0 and
// one of the following two
// conditions is true:
// a) mid is equal to low
// b) f(mid-1) is negative
if (f(mid) > 0 && (mid == low || f(mid-1) <= 0))
return mid;
// If f(mid) is smaller than or equal to 0
if (f(mid) <= 0)
return binarySearch((mid + 1), high);
else // f(mid) > 0
return binarySearch(low, (mid -1));
}
/* Return -1 if there is no positive
value in given range */
return -1;
}
// driver code
public static void main(String[] args)
{
System.out.print ("The value n where f() "+
"becomes positive first is "+
findFirstPositive());
}
}
// This code is contributed by rishabh_jain
Python3
# Python3 program for Unbound Binary search.
# Let's take an example function as
# f(x) = x^2 - 10*x - 20
# Note that f(x) can be any monotonically
# increasing function
def f(x):
return (x * x - 10 * x - 20)
# Returns the value x where above function
# f() becomes positive first time.
def findFirstPositive() :
# When first value itself is positive
if (f(0) > 0):
return 0
# Find 'high' for binary search
# by repeated doubling
i = 1
while (f(i) <= 0) :
i = i * 2
# Call binary search
return binarySearch(i/2, i)
# Searches first positive value of
# f(i) where low <= i <= high
def binarySearch(low, high):
if (high >= low) :
# mid = (low + high)/2
mid = low + (high - low)/2;
# If f(mid) is greater than 0
# and one of the following two
# conditions is true:
# a) mid is equal to low
# b) f(mid-1) is negative
if (f(mid) > 0 and (mid == low or f(mid-1) <= 0)) :
return mid;
# If f(mid) is smaller than or equal to 0
if (f(mid) <= 0) :
return binarySearch((mid + 1), high)
else : # f(mid) > 0
return binarySearch(low, (mid -1))
# Return -1 if there is no positive
# value in given range
return -1;
# Driver Code
print ("The value n where f() becomes "+
"positive first is ", findFirstPositive());
# This code is contributed by rishabh_jain
C#
// C# program for Binary Search
using System;
class Binary
{
public static int f(int x)
{
return (x*x - 10*x - 20);
}
// Returns the value x where above
// function f() becomes positive
// first time.
public static int findFirstPositive()
{
// When first value itself is positive
if (f(0) > 0)
return 0;
// Find 'high' for binary search
// by repeated doubling
int i = 1;
while (f(i) <= 0)
i = i * 2;
// Call binary search
return binarySearch(i / 2, i);
}
// Searches first positive value of
// f(i) where low <= i <= high
public static int binarySearch(int low, int high)
{
if (high >= low)
{
/* mid = (low + high)/2 */
int mid = low + (high - low)/2;
// If f(mid) is greater than 0 and
// one of the following two
// conditions is true:
// a) mid is equal to low
// b) f(mid-1) is negative
if (f(mid) > 0 && (mid == low ||
f(mid-1) <= 0))
return mid;
// If f(mid) is smaller than or equal to 0
if (f(mid) <= 0)
return binarySearch((mid + 1), high);
else
// f(mid) > 0
return binarySearch(low, (mid -1));
}
/* Return -1 if there is no positive
value in given range */
return -1;
}
// Driver code
public static void Main()
{
Console.Write ("The value n where f() " +
"becomes positive first is " +
findFirstPositive());
}
}
// This code is contributed by nitin mittal
PHP
<?php
// PHP program for Binary Search
// Let's take an example function
// as f(x) = x^2 - 10*x - 20
// Note that f(x) can be any
// monotonically increasing function
function f($x)
{
return ($x * $x - 10 * $x - 20);
}
// Returns the value x where above
// function f() becomes positive
// first time.
function findFirstPositive()
{
// When first value
// itself is positive
if (f(0) > 0)
return 0;
// Find 'high' for binary
// search by repeated doubling
$i = 1;
while (f($i) <= 0)
$i = $i * 2;
// Call binary search
return binarySearch(intval($i / 2), $i);
}
// Searches first positive value
// of f(i) where low <= i <= high
function binarySearch($low, $high)
{
if ($high >= $low)
{
/* mid = (low + high)/2 */
$mid = $low + intval(($high -
$low) / 2);
// If f(mid) is greater than 0
// and one of the following two
// conditions is true:
// a) mid is equal to low
// b) f(mid-1) is negative
if (f($mid) > 0 && ($mid == $low ||
f($mid - 1) <= 0))
return $mid;
// If f(mid) is smaller
// than or equal to 0
if (f($mid) <= 0)
return binarySearch(($mid + 1), $high);
else // f(mid) > 0
return binarySearch($low, ($mid - 1));
}
/* Return -1 if there is no
positive value in given range */
return -1;
}
// Driver Code
echo "The value n where f() becomes ".
"positive first is ".
findFirstPositive() ;
// This code is contributed by Sam007
?>
Javascript
<script>
// Javascript program for Binary Search
function f(x)
{
return (x*x - 10*x - 20);
}
// Returns the value x where above
// function f() becomes positive
// first time.
function findFirstPositive()
{
// When first value itself is positive
if (f(0) > 0)
return 0;
// Find 'high' for binary search
// by repeated doubling
let i = 1;
while (f(i) <= 0)
i = i * 2;
// Call binary search
return binarySearch(parseInt(i / 2, 10), i);
}
// Searches first positive value of
// f(i) where low <= i <= high
function binarySearch(low, high)
{
if (high >= low)
{
/* mid = (low + high)/2 */
let mid = low + parseInt((high - low)/2, 10);
// If f(mid) is greater than 0 and
// one of the following two
// conditions is true:
// a) mid is equal to low
// b) f(mid-1) is negative
if (f(mid) > 0 && (mid == low ||
f(mid-1) <= 0))
return mid;
// If f(mid) is smaller than or equal to 0
if (f(mid) <= 0)
return binarySearch((mid + 1), high);
else
// f(mid) > 0
return binarySearch(low, (mid -1));
}
/* Return -1 if there is no positive
value in given range */
return -1;
}
document.write ("The value n where f() " +
"becomes positive first is " +
findFirstPositive());
</script>
Producción :
The value n where f() becomes positive first is 12
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA