Форум программистов, компьютерный форум, киберфорум
Наши страницы

Бинарный поиск - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Компиляция gcc http://www.cyberforum.ru/cpp-beginners/thread993197.html
Подскажите как в VS скомпилировать программу с помощью компилятора gcc
C++ Почему изменение элемента массива, который был объявлен с размером [] - это UB? char str = "zzarb"; str = 'm'; // Undefined Behavior char str = "zzarb"; str = 'm'; // OK Что-то я не пойму, почему тогда все нормально, если указать размер вручную, а не давать компилятору... http://www.cyberforum.ru/cpp-beginners/thread993182.html
C++ Ошибка: "Expression must be modifiable lvalue"
Всем привет. Есть одна проблемка. vs2010 выдает ошибку в строке 20 Error: Expression must be modifiable lvalue. Также в строке 51 Error: Expression must have pointer-to-object type. В чем проблема?...
C++ Преобразование строки в имя типа
Дали задание - разработать контейнер. С этим проблем не было, но далее для тестирования понадобилось каким-то образом ввести тип данных, хранящихся в нём с клавиатуры. Даже не представляю как это...
C++ Как регулярно считывать последнюю строку в файле http://www.cyberforum.ru/cpp-beginners/thread993170.html
Добрый день. Имеется текстовый файл. Он постоянно обновляется и в его конец дописываются строки. Необходимо считывать новую строку непосредственно в string, как только она появляется в файле. Вот и...
C++ Заменить все пробелы на запятые, а запятые на точки. Посчитать количество запятых во введенной строке Во введенной строке заменить все пробелы на запятые, а запятые на точки. Посчитать количество запятых во введенной строке. Нужно написать программу. Заранее благодарен. подробнее

Показать сообщение отдельно
Tima0406
0 / 0 / 0
Регистрация: 26.10.2013
Сообщений: 4

Бинарный поиск - C++

30.10.2013, 23:09. Просмотров 214. Ответов 0
Метки (Все метки)

Всем привет. Есть такая проблемка. Не работает бинарный поиск после сортировки массива подсчетом. Помогите, пожалуйста!
#include <iostream>

using namespace std;

class Bubble
{
public:
int N;
int M;
int *arr;
int *out;
Bubble()
{
cout<< "Input number of keys: \n";
cin>> N;
cout<< "Input number of keys for binary search: \n";
cin>> M;
arr = new int[N];
out = new int[N];
}
void input();
void bubbleSort();
int binary(int);
void output();
};

void Bubble::input()
{
cout<< "Input keys: \n";
int k;
for (int i = 0; i< N; i++)
{
cin>>arr[i];
}
cout<< "Initial array: \n";
for (int i = 0; i< N; i++)
cout<<arr[i] << " ";
}

void Bubble::bubbleSort()
{
int max=arr[0];

for (int i=1;i<N;i++) {
if (arr[i]>max) {
max=arr[i];
}
}

for (int i=0;i<N;i++) {
out[i]=0;
}
int *temp=new int[max+1];
for (int i=0;i<max+1;i++) {
temp[i]=0;
}
for (int i=0;i<N;i++){
temp[arr[i]]=temp[arr[i]]+1;
}
for (int i=1;i<max+1;i++) {
temp[i]=temp[i]+temp[i-1];
}
for (int i=N-1;i>=0;i--) {
out[temp[arr[i]]-1]=arr[i];
temp[arr[i]]=temp[arr[i]]-1;
}

}

int Bubble::binary(int x)
{
int low, high, mid;

low = 0;
high = N - 1;
while(low <= high)
{
mid = (low + high) / 2;
if(x <arr[mid])
high = mid - 1;
else if(x >arr[mid])
low = mid + 1;
else
return mid;
}
return -1;
}

void Bubble::output()
{
int k;
cout<< "\n" << "Sorted array: \n";
for (int i = 0; i< N; i++)
cout<<out[i] << " ";
for (int j = 0; j < M; j++)
{
cout<< "\n" << "Input key for search: \n";
cin>> k;
if(binary(k) < 0)
cout<< "There is no such key!\n";
else
cout<< "The index of the key is: " << binary(k) + 1 << "\n";
}
}

int main()
{
Bubble b;
b.input();
b.bubbleSort();
b.output();

}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru