Форум программистов, компьютерный форум CyberForum.ru

Приближенный двоичный поиск - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Матрицу произвольного размера преобразовать в вектор http://www.cyberforum.ru/cpp-beginners/thread917140.html
ребят такое дело. сам с++ норм знаю, но давно не работал (1 год) все по забывал вот снова понадобилось. короче нужно матрицу произвольного размера преобразовать в вектор. я знаю что есть инклуд вектор и др., но с ними заморачиваться не хочу ибо, когда работал постоянно на с++ не особо вьезжал а сейчас вообще) короче прога что то не то делает, очен надеюсь на вашу помощь, может я чего намудрил....
C++ Для чего тут этот массив ? Народ в общем ситуация такая я учу С++ по книге Герберт Шилдта (C++: базовый курс, 3-е издание) там в книге есть пример на использование строковых массивов вот мне интересно какую функцию в коде выполняет массив char temp; который находится в функции : enter() ? Заранее благодарствую за ответ ! //Программа ведения баз данных служащих #include <iostream> http://www.cyberforum.ru/cpp-beginners/thread917128.html
Подскажите по коду (классы) C++
Ребята! Помогите создать код на C++ до завтрашнего дня (до 9 утра по мск)! Заранее спасибо!
C++ Метод хорд в решении простецкой параболы
Доброго времени суток. При решении, например на промежутке выводит количество итераций, равное 9ти, хотя находит корень за 4 итерации. Подскажите что делать и где таится подлянка. Может зацикливается? Хотя показывается один и тот же результат... Вот файлы: 1) файл chords.cpp #include "stdafx.h" #include "description.h" #include <iostream> #include <iomanip> #include <cmath> using...
C++ пожалуйста подскажите для ЭКЗАМЕНА http://www.cyberforum.ru/cpp-beginners/thread917113.html
Здравствуйте, меня на экзамене завалили, а я в си++ новичок и пока что не соображаю особо. помогите пожалуйста это решить. я не понимаю как написать код по этому выражению. фотографию прикрепил .завтра пересдача и нужно это принести. заранее огромное спасибо
C++ производная Здравствуйте, подскажите пожалуйста, можно ли как-нибудь найти производную от функции с переменной, не прибегая к каким-то супер сложным путям? А если без них никак, подскажите идею. Заранее спасибо! подробнее

Показать сообщение отдельно
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
03.07.2013, 22:53     Приближенный двоичный поиск
ann-joker, rofl ! у вас не двоичный поиск, а линейный ! У вас прога срабатывает за О(N*K), а требуется O(K * LogN) !

Добавлено через 1 минуту
Цитата Сообщение от ann-joker Посмотреть сообщение
N и K (0 > N,K >100001 )
тут наверное вот так:
0 < N, K < 100001

Набросал вот. Надеюсь, что правильно.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cmath>
 
using namespace std;
 
int n;
int a[100002];
 
int closest(int c) {
    int l = 0, r = n - 1;
    for (int i = 0; i < 100; ++i) {
        int mid = (r + l) / 2;
        if (a[mid] > c)
            r = mid;
        else
            l = mid;
    }
    if (l != r)
        return (abs(a[r] - c) < abs(a[l] - c) ? r : l);
    return l;
}
 
int main() {
    int k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    for (int i = 0, c; i < k; ++i)
        scanf("%d", &c), printf("%d ", a[closest(c)]);
    return 0;
}
 
Текущее время: 03:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru