Рубрики

Пример неограниченного двоичного поиска (Найти точку, в которой монотонно возрастающая функция впервые становится положительной)

Дана функция 'int f (unsigned int x)', которая принимает неотрицательное целое число 'x' в качестве входных данных и возвращает целое число в качестве выходных данных. Функция монотонно возрастает по отношению к значению x, т.е. значение f (x + 1) больше, чем f (x) для каждого входа x. Найдите значение n, где f () становится положительным в первый раз. Поскольку f () монотонно возрастает, значения f (n + 1), f (n + 2),… должны быть положительными, а значения f (n-2), f (n-3), .. должны быть отрицательными ,
Найти n за время O (logn), вы можете предположить, что f (x) можно оценить за время O (1) для любого входа x.

Простое решение состоит в том, чтобы начать с i, равного 0, и один за другим вычислить значение f (i) для 1, 2, 3, 4 и т. Д., Пока мы не найдем положительное значение f (i). Это работает, но занимает O (N) время.

Можем ли мы применить Бинарный поиск, чтобы найти n за O (Logn) время? Мы не можем напрямую применять бинарный поиск, поскольку у нас нет верхнего предела или высокого индекса. Идея состоит в том, чтобы делать повторное удвоение до тех пор, пока мы не найдем положительное значение, то есть проверить значения 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.

Можем ли мы применить бинарный поиск, чтобы найти n после нахождения 'high'? Мы можем применить бинарный поиск сейчас, мы можем использовать «высокий / 2» как низкий и «высокий» как высокие индексы в бинарном поиске. Результат n должен находиться между 'high / 2' и 'high'.

Количество шагов для нахождения «высокий» O (Logn). Таким образом, мы можем найти «высоко» в O (Logn) времени. Как насчет времени, которое занимает бинарный поиск между высоким / 2 и высоким? Значение 'high' должно быть меньше 2 * n. Количество элементов между высоким / 2 и высоким должно быть O (n). Следовательно, временная сложность бинарного поиска равна O (Logn), а общая временная сложность составляет 2 * O (Logn), которая равна O (Logn).

C ++

// C ++ код для бинарного поиска
#include<bits/stdc++.h> 

using namespace std;

  

int binarySearch(int low, int high); // опытный образец

  
// Давайте возьмем пример функции
// так как f (x) = x ^ 2 - 10 * x - 20 Обратите внимание, что
// f (x) может быть любой монотонно возрастающей функцией

int f(int x) { return (x*x - 10*x - 20); } 

  
// Возвращает значение х где выше
// функция f () становится положительной
// первый раз.

int findFirstPositive() 

    // Когда первое значение само по себе положительно

    if (f(0) > 0) 

        return 0; 

  

    // Найти 'high' для бинарного поиска путем повторного удвоения

    int i = 1; 

    while (f(i) <= 0) 

        i = i*2; 

  

    // Вызываем бинарный поиск

    return binarySearch(i/2, i); 

  
// Ищет первое положительное значение
// из f (i) где низкий <= i <= высокий

int binarySearch(int low, int high) 

    if (high >= low) 

    

        int mid = low + (high - low)/2; / * средний = (низкий + высокий) / 2 * /

  

        // Если f (середина) больше 0 и

        // один из следующих двух

        // условия верны:

        // а) середина равна низкой

        // б) f (середина 1) отрицательна

        if (f(mid) > 0 && (mid == low || f(mid-1) <= 0)) 

            return mid; 

  

        // Если f (mid) меньше или равно 0

        if (f(mid) <= 0) 

            return binarySearch((mid + 1), high); 

        else // f (середина)> 0

            return binarySearch(low, (mid -1)); 

    

  

    / * Вернуть -1, если нет

    положительное значение в заданном диапазоне * /

    return -1; 

  
/ * Код водителя * /

int main() 

    cout<<"The value n where f() becomes" <<

        "positive first is "<< findFirstPositive(); 

    return 0; 

}

  
// Этот код предоставлен rathbhupendra

С

#include <stdio.h>

int binarySearch(int low, int high); // опытный образец

  
// Давайте возьмем пример функции как f (x) = x ^ 2 - 10 * x - 20
// Обратите внимание, что f (x) может быть любой монотонно увеличивающейся функцией

int f(int x) { return (x*x - 10*x - 20); }

  
// Возвращает значение x, где вышеуказанная функция f () становится положительной
// первый раз.

int findFirstPositive()

{

    // Когда первое значение само по себе положительно

    if (f(0) > 0)

        return 0;

  

    // Найти 'high' для бинарного поиска путем повторного удвоения

    int i = 1;

    while (f(i) <= 0)

        i = i*2;

  

    // Вызываем бинарный поиск

    return binarySearch(i/2, i);

}

  
// Поиск первого положительного значения f (i), где low <= i <= high

int binarySearch(int low, int high)

{

    if (high >= low)

    {

        int mid = low + (high - low)/2; / * средний = (низкий + высокий) / 2 * /

  

        // Если f (mid) больше 0 и один из следующих двух

        // условия верны:

        // а) середина равна низкой

        // б) f (середина 1) отрицательна

        if (f(mid) > 0 && (mid == low || f(mid-1) <= 0))

            return mid;

  

        // Если f (mid) меньше или равно 0

        if (f(mid) <= 0)

            return binarySearch((mid + 1), high);

        else // f (середина)> 0

            return binarySearch(low, (mid -1));

    }

  

    / * Вернуть -1, если в данном диапазоне нет положительного значения * /

    return -1;

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    printf("The value n where f() becomes positive first is %d",

           findFirstPositive());

    return 0;

}

Джава

// Java-программа для бинарного поиска

import java.util.*;

  

class Binary

{

    public static int f(int x) 

    { return (x*x - 10*x - 20); }

  

    // Возвращает значение х где выше

    // функция f () становится положительной

    // первый раз.

    public static int findFirstPositive()

    {

        // Когда первое значение само по себе положительно

        if (f(0) > 0)

            return 0;

  

        // Найти 'high' для бинарного поиска

        // повторным удвоением

        int i = 1;

        while (f(i) <= 0)

            i = i * 2;

  

        // Вызываем бинарный поиск

        return binarySearch(i / 2, i);

    }

  

    // Ищет первое положительное значение

    // f (i) где низкий <= i <= высокий

    public static int binarySearch(int low, int high)

    {

        if (high >= low)

        {   

            / * средний = (низкий + высокий) / 2 * /

            int mid = low + (high - low)/2

  

            // Если f (середина) больше 0 и

            // один из следующих двух

            // условия верны:

            // а) середина равна низкой

            // б) f (середина 1) отрицательна

            if (f(mid) > 0 && (mid == low || f(mid-1) <= 0))

                return mid;

  

            // Если f (mid) меньше или равно 0

            if (f(mid) <= 0)

                return binarySearch((mid + 1), high);

            else // f (середина)> 0

                return binarySearch(low, (mid -1));

        }

  

        / * Вернуть -1, если нет положительного

        значение в заданном диапазоне * /

        return -1;

    }

      

    // код драйвера

    public static void main(String[] args)

    {

        System.out.print ("The value n where f() "+

                         "becomes positive first is "+

                         findFirstPositive());

    }

}

  
// Этот код предоставлен rishabh_jain

python3

# Python3 программа для несвязанного бинарного поиска.

  
# Давайте возьмем пример функции как
# f (x) = x ^ 2 - 10 * x - 20
# Обратите внимание, что f (x) может быть любым монотонно
# функция увеличения

def f(x): 

    return (x * x - 10 * x - 20)

  
# Возвращает значение х где выше функции
# f () становится положительным с первого раза.

def findFirstPositive() :

      

    # Когда первое значение само по себе положительно

    if (f(0) > 0):

        return 0

  

    # Найти 'high' для бинарного поиска

    # повторным удвоением

    i = 1

    while (f(i) <= 0) :

        i = i * 2

  

    # Вызов бинарного поиска

    return binarySearch(i/2, i)

  
# Ищет первое положительное значение
# f (i) где низкий <= i <= высокий

def binarySearch(low, high):

    if (high >= low) :

          

        # средний = (низкий + высокий) / 2

        mid = low + (high - low)/2;  

  

        # Если f (середина) больше 0

        # и один из следующих двух

        # условия верны:

        # a) mid равно low

        # b) f (середина 1) отрицательна

        if (f(mid) > 0 and (mid == low or f(mid-1) <= 0)) :

            return mid;

  

        # Если f (середина) меньше или равно 0

        if (f(mid) <= 0) :

            return binarySearch((mid + 1), high)

        else : # f (середина)> 0

            return binarySearch(low, (mid -1))

      

    # Вернуть -1, если нет положительного

    # значение в заданном диапазоне

    return -1;

  
Код водителя

print ("The value n where f() becomes "+

      "positive first is ", findFirstPositive());

  
# Этот код предоставлен rishabh_jain

C #

// C # программа для бинарного поиска

using System;

  

class Binary

{

    public static int f(int x) 

    

        return (x*x - 10*x - 20); 

    }

  

    // Возвращает значение х где выше

    // функция f () становится положительной

    // первый раз.

    public static int findFirstPositive()

    {

        // Когда первое значение само по себе положительно

        if (f(0) > 0)

            return 0;

  

        // Найти 'high' для бинарного поиска

        // повторным удвоением

        int i = 1;

        while (f(i) <= 0)

            i = i * 2;

  

        // Вызываем бинарный поиск

        return binarySearch(i / 2, i);

    }

  

    // Ищет первое положительное значение

    // f (i) где низкий <= i <= высокий

    public static int binarySearch(int low, int high)

    {

        if (high >= low)

        

            / * средний = (низкий + высокий) / 2 * /

            int mid = low + (high - low)/2; 

  

            // Если f (середина) больше 0 и

            // один из следующих двух

            // условия верны:

            // а) середина равна низкой

            // б) f (середина 1) отрицательна

            if (f(mid) > 0 && (mid == low ||

                             f(mid-1) <= 0))

                return mid;

  

            // Если f (mid) меньше или равно 0

            if (f(mid) <= 0)

                return binarySearch((mid + 1), high);

            else 

              

                // f (середина)> 0

                return binarySearch(low, (mid -1));

        }

  

        / * Вернуть -1, если нет положительного

        значение в заданном диапазоне * /

        return -1;

    }

      

    // Код драйвера

    public static void Main()

    {

       Console.Write ("The value n where f() " +

                      "becomes positive first is " +

                       findFirstPositive());

    }

}

  
// Этот код предоставлен нитин митталь

PHP

<?php
// PHP программа для бинарного поиска

  
// Давайте возьмем пример функции
// так как f (x) = x ^ 2 - 10 * x - 20
// Обратите внимание, что f (x) может быть любым
// монотонно возрастающая функция

function f($x

    return ($x * $x - 10 * $x - 20); 

}

  
// Возвращает значение х где выше
// функция f () становится положительной
// первый раз.

function findFirstPositive()

{

    // Когда первое значение

    // сам позитив

    if (f(0) > 0)

        return 0;

  

    // Найти 'high' для двоичного файла

    // поиск по повторному удвоению

    $i = 1;

    while (f($i) <= 0)

        $i = $i * 2;

  

    // Вызываем бинарный поиск

    return binarySearch(intval($i / 2), $i);

}

  
// Ищет первое положительное значение
// из f (i) где низкий <= i <= высокий

function binarySearch($low, $high)

{

    if ($high >= $low)

    {

        / * средний = (низкий + высокий) / 2 * /

        $mid = $low + intval(($high

                              $low) / 2); 

  

        // Если f (середина) больше 0

        // и один из следующих двух

        // условия верны:

        // а) середина равна низкой

        // б) f (середина 1) отрицательна

        if (f($mid) > 0 && ($mid == $low || 

                          f($mid - 1) <= 0))

            return $mid;

  

        // Если f (середина) меньше

        // чем или равно 0

        if (f($mid) <= 0)

            return binarySearch(($mid + 1), $high);

        else // f (середина)> 0

            return binarySearch($low, ($mid - 1));

    }

  

    / * Вернуть -1, если нет

    положительное значение в заданном диапазоне * /

    return -1;

}

  
// Код драйвера

echo "The value n where f() becomes "

                 "positive first is "

                 findFirstPositive() ;

  
// Этот код предоставлен Sam007
?>


Выход :

The value n where f() becomes positive first is 12

Связанная статья:
Экспоненциальный поиск

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Пример неограниченного двоичного поиска (Найти точку, в которой монотонно возрастающая функция впервые становится положительной)

0.00 (0%) 0 votes