იპოვნეთ წერტილი, სადაც მონოტონურად მზარდი ფუნქცია პირველად ხდება პოზიტიური  


Რთული ტური საშუალო
ხშირად ეკითხებიან American Express
ორობითი ძებნა Დაყავი და იბატონე Searching

პრობლემის განცხადება  

”იპოვნეთ წერტილი, სადაც მონოტონურად მზარდი ფუნქცია პირველად ხდება პოზიტიური” ჩვენ მივეცით ფუნქცია ”Int f (ხელმოუწერელი int x)” რომელიც იღებს ა არაუარყოფითი მთელი რიცხვი 'x' შეყვანის სახით და აბრუნებს an- ს მთელი რიცხვი როგორც გამომავალი. ფუნქცია ერთფეროვნად იზრდება x მნიშვნელობასთან მიმართებაში, ანუ f (x + 1) მნიშვნელობა f (x) - ზე მეტია x x შეყვანისთვის. იპოვნეთ მნიშვნელობა 'n' სადაც f () პირველად ხდება პოზიტიური. რადგან f () ერთფეროვნად იზრდება, f (n + 1), f (n + 2), values ​​უნდა იყოს დადებითი, ხოლო f (n-2), f (n-3), .. უნდა იყოს უარყოფითი . ჩვენი მიზანია O (logn) დროში ვიპოვოთ n. თქვენ შეიძლება ჩათვალოთ, რომ f (x) შეიძლება შეფასდეს O (1) დროში ნებისმიერი x შეყვანისთვის.

შეყვანის ფორმატი  

F და x ფუნქციის შემცველი პირველი და ერთადერთი სტრიქონი.

Გამავალი ფორმატი  

მთელი და მხოლოდ ერთი სტრიქონი, რომელიც შეიცავს მთელი რიცხვის მნიშვნელობას, აღნიშნავს წერტილს, სადაც მონოტონურად მზარდი ფუნქცია ხდება პირველად პოზიტიური.

მაგალითი  

x^2 - 4x - 8
6

განმარტება: მნიშვნელობა x სადაც f (x) ხდება დადებითი არის 6.

ალგორითმი  

ამ მეთოდით, მთავარი იდეა არის ორობითი ძიების გამოყენება, მაგრამ ორობითი ძიებისთვის, ჩვენ გვჭირდება დაბალი და მაღალი მნიშვნელობები. ქვემოთ algo გვიჩვენებს, თუ როგორ უნდა იპოვოთ მნიშვნელობები და განვახორციელოთ ორობითი ძებნა.

იხილეთ ასევე
შეცვალეთ მასივი რიცხვების პერმუტაციად 1 – დან N– მდე

1. სანამ f (i) მეტია ნულზე, გაორმაგეთ i მნიშვნელობა. მას შემდეგ, რაც f (i) ნულზე მეტია, მაშინ ავიღოთ i როგორც მაღალი და i / 2 როგორც დაბალი.

2. ახლა მოძებნეთ f (i) - ის პირველი დადებითი მნიშვნელობა i / 2-სა და i- ს შორის. ორობითი ძებნა

3. სანამ მაღალი უფრო მაღალია ან ტოლი მაღალი, იპოვნე შუა რიცხვები

  • თუ f (შუა) ნულზე მეტია, ხოლო შუა უდრის დაბალს ან f (შუა -1) ნაკლებია ან ტოლია ნულის, ანუ f (შუა> 0) && (შუა == დაბალი || f (შუა 1) ) <= 0), შემდეგ დაბრუნდით შუა რიცხვებში
  • თუ f (შუა რიცხვებში) ნულზე ნაკლებია, მაშინ რეკურსიულად მოძებნეთ მარჯვენა ნახევარში.
  • თუ f (შუა რიცხვი) ნულზე მეტია, რეკურსიულად მოძებნეთ მარცხენა ნახევარში.

განხორციელება  

C ++ პროგრამა, რომ იპოვოთ წერტილი, სადაც მონოტონურად მზარდი ფუნქცია პირველად ხდება პოზიტიური

#include<bits/stdc++.h> 
using namespace std; 

int binarySearch(int low, int high); 
int f(int x) 
{ 
    return (x*x - 10*x - 20); 
} 

int findFirstPositive() 
{ 
  if (f(0) > 0) 
    return 0; 
  int i = 1; 
  while (f(i) <= 0) 
    i = i*2; 
  return binarySearch(i/2, i); 
} 

int binarySearch(int low, int high) 
{ 
  if (high >= low) 
  { 
    int mid = low + (high - low)/2; 
    if (f(mid) > 0 && (mid == low || f(mid-1) <= 0)) 
      return mid; 

    if (f(mid) <= 0) 
      return binarySearch((mid + 1), high); 
    else  
      return binarySearch(low, (mid -1)); 
  } 
  return -1; 
} 

int main() 
{ 
  cout<<findFirstPositive(); 
  return 0; 
}

ჯავა პროგრამა, რომ იპოვოთ წერტილი, სადაც მონოტონურად მზარდი ფუნქცია პირველად ხდება პოზიტიური

import java.util.ArrayList;
import java.util.Scanner;
class sum
{
    public static int f(int x)  
    { 
        return (x*x - 10*x - 20);
    } 
    public static int findFirstPositive() 
    { 
        if(f(0)>0)
        {
            return 0;
        }
        int i = 1; 
        while(f(i)<=0) 
            i = i * 2; 
        return binarySearch(i / 2, i); 
    } 
    public static int binarySearch(int low, int high) 
    { 
        if (high >= low) 
        {    
            int mid = low + (high - low)/2;  
            if (f(mid) > 0 && (mid == low || f(mid-1) <= 0)) 
                return mid; 
            if (f(mid) <= 0) 
                return binarySearch((mid + 1), high); 
            else 
                return binarySearch(low, (mid -1)); 
        }
        return -1;
    }
    public static void main(String[] args)
    {
        Scanner sr = new Scanner(System.in);
        findFirstPositive();
    }
}
x*x - 10*x - 20
12

სირთულის ანალიზი  

დროის სირთულე

O (logn): ნაბიჯების რაოდენობა "მაღალი" -ს მოსაძებნად არის O (Logn). ასე რომ, ჩვენ შეგვიძლია ვპოვოთ 'მაღალი' O (Logn) დროში. რაც შეეხება ორობითი ძიების დროს მაღალ / 2-სა და მაღალს შორის გატარებულ დროს? "მაღალი" -ს მნიშვნელობა უნდა იყოს 2 * n -ზე ნაკლები. ელემენტების რაოდენობა მაღალ / 2-სა და მაღალს შორის უნდა იყოს O (n). ამიტომ, ორობითი ძიების დროის სირთულეა O (Logn) და საერთო სირთულეა 2 * O (Logn), რაც O (Logn)

იხილეთ ასევე
მაქსიმალური ჯამის მართკუთხედი 2D მატრიცაში

სივრცის სირთულე

O (1) რადგან ჩვენ აქ არანაირ დამხმარე ადგილს არ ვქმნით.