给定一个函数“int f（unsigned int x）”，它取 非负整数 “x”作为输入并返回 整数 作为输出。函数相对于x的值是单调递增的，即对于每个输入x，f（x+1）的值大于f（x）。找到值“n”，其中f（）第一次变为正。因为f（）是单调递增的，所以f（n+1），f（n+2），…的值必须是正的，而f（n-2），f（n-3），…的值必须是负的。 在O（logn）时间内求n，你可以假设f（x）可以在O（1）时间内对任何输入x求值。
null
A. 简单解决方案 从i等于0开始，逐个计算f（i）的值，1，2，3，4…等等，直到我们找到一个正的f（i）。这是可行的，但需要花费很多时间。 我们能用二进制搜索在O（Logn）时间内找到n吗？ 我们不能直接应用二进制搜索，因为我们没有上限或高索引。这个想法是重复加倍，直到我们找到一个正值，也就是说，检查f（）的值，直到f（i）变为正值。
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.
在找到“high”之后，我们可以应用二进制搜索来找到n吗？我们现在可以应用二进制搜索，我们可以在二进制搜索中使用’high/2’作为低索引，使用’high’作为高索引。结果n必须介于“高/2”和“高”之间。 查找“高”的步骤数为O（Logn）。所以我们可以在O（Logn）时间中找到“high”。在high/2和high之间进行二进制搜索所需的时间是多少？“high”的值必须小于2*n。high/2和high之间的元素数必须为O（n）。因此，二进制搜索的时间复杂度为O（Logn），总体时间复杂度为2*O（Logn），即O（Logn）。
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> |
输出：
The value n where f() becomes positive first is 12
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
