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

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

Восстановить пароль Регистрация
 
Tima0406
0 / 0 / 0
Регистрация: 26.10.2013
Сообщений: 4
30.10.2013, 23:09     Бинарный поиск #1
Всем привет. Есть такая проблемка. Не работает бинарный поиск после сортировки массива подсчетом. Помогите, пожалуйста!
#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();

}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.10.2013, 23:09     Бинарный поиск
Посмотрите здесь:

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

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 07:57. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru