Монотонды түрде өсетін функция бірінші рет оң болатын нүктені табыңыз


Күрделілік дәрежесі орта
Жиі кіреді American Express
Екілік іздеу Бөліңіз және жеңіңіз іздеу

Проблемалық мәлімдеме

«Монотонды түрде өсетін функция бірінші рет оң болатын нүктені табыңыз», біз функция бердік “Int f (unsigned int x)” бұл а теріс емес бүтін сан 'x' кіріс ретінде және an қайтарады бүтін сан шығыс ретінде. The функция х-тің мәніне қатысты монотонды түрде жоғарылайды, яғни f (x + 1) мәні x (f) -тен әр x кірісі үшін үлкен болады. F () бірінші рет оңға айналатын 'n' мәнін табыңыз. F () монотонды түрде өсетін болғандықтан, f (n + 1), f (n + 2),… ​​мәндері оң, ал f (n-2), f (n-3), .. мәндері теріс болуы керек. . Біздің мақсатымыз O (logn) уақытында n табу. F (x) кез келген x кірісі үшін O (1) уақыт ішінде бағаланады деп ойлауға болады.

Кіріс форматы

F (x) функциясын қамтитын бірінші және жалғыз жол.

Шығу форматы

Бүтін мәнді қамтитын бірінші және жалғыз жол монотонды түрде өсетін функция бірінші рет оңға айналатын нүктені білдіреді.

мысал

x^2 - 4x - 8
6

Түсіндіру: X мәні, онда f (x) оңға айналады 6.

Алгоритм

Бұл әдісте негізгі идея екілік іздеуді қолдану болып табылады, бірақ екілік іздеу үшін бізге төмен және жоғары мәндер қажет. Algo астында мәндерді қалай табуға болатынын және екілік іздеуді қалай жүзеге асыратындығын көрсетеді.

1. F (i) нөлге дейін, i мәнін екі есеге арттырыңыз. Егер f (i) нөлден үлкен болса, онда i-ді жоғарыға, ал i / 2-ді төменге алыңыз.

2. Енді i / 2 мен i аралығындағы f (i) бірінші оң мәнін іздеңіз. Екілік іздеу

3. Жоғарыдан жоғарыға немесе үлкенге тең болғанша ортаны табыңыз

  • Егер f (ортасы) нөлден үлкен болса және ортасы төменге тең болса немесе f (ортасы -1) нөлге тең немесе тең болса, яғни f (ортасы> 0) && (ортасы == төмен || f (ортасы-1) ) <= 0), содан кейін ортасына оралыңыз
  • Егер f (орта) нөлден аз болса, онда оң жақ жартысында рекурсивті түрде іздеңіз.
  • Егер f (ортасы) нөлден үлкен болса, онда сол жақ жартысында рекурсивті түрде іздеңіз.

Іске асыру

С ++ бағдарламасы монотонды өсетін функция бірінші рет оң болатын нүктені табуға арналған

#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; 
}

Java бағдарламасы монотонды түрде өсетін функция бірінші рет оң болатын нүктені табады

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), ал жалпы уақыттық күрделілік O * (Logn) болатын 2 * O (Logn) құрайды.

Ғарыштың күрделілігі

O (1) өйткені біз бұл жерде ешқандай көмекші кеңістік жасамаймыз.