VPF::Бинарный поиск в упорядоченном массиве

Voldemar2004

Дата 29.3.2006, 23:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1650
Регистрация: 25.12.2004

Репутация: нет
Всего: 23

Создал структуру. Знаю, как делать обычный поиск. Не могу понять, как работает бинарный поиск. Обрывки сведений о том, что его надо делить пополам. Может кто объяснит сам принцип бинарного поиска? smile

Код


#include <iostream.h>
#include <conio.h>

int main(int argc, char* argv[])
{

struct tVipusknik{
        char Fam[20];
        char Name[20];
        char Otch[20];
        char VUZ[20];
        char Spec[20];
        int GOD;
};

tVipusknik f[10];

int VipCount;
cout<<"Vvedite kolichestvo vipusknikov: ";
cin>>VipCount;

cout<<"\n"<<"Vvedite FIO Vipusknika, nazvanie VUZ'a, specialnost i god okonchaniya";

for(int i=0; i<VipCount; i++)
{
cout<<"\n"<<"Fam: "; cin>>f[i].Fam;

cout<<"\n"<<"Name: "; cin>>f[i].Name;

cout<<"\n"<<"Otch: "; cin>>f[i].Otch;

cout<<"\n"<<"Vuz: "; cin>>f[i].VUZ;

cout<<"\n"<<"Spec: "; cin>>f[i].Spec;

cout<<"\n"<<"God okonchaniya: "; cin>>f[i].GOD;
}

getch();

return 0;
}

--------------------

i_i
(';')
(V)

user posted image

cardinal

Дата 30.3.2006, 00:10 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 2
Всего: 99

У тебя упорядоченный массив с числами
2, 6, 23, 26, 45, 67, 78, 79, 83, 89, 97, 100
Тебе надо узнать есть ли в массиве число 89 и вернуть его индекс.

Серединный элемент это допустим 67. Ты его сравниваешь с 89 и понимаешь, что число должно быть "правее" текущего элемента. Делишь правый кусок пополам и попадаешь на 83. Число должно быть опять "правее". ... Попадаешь на 97. Число должно быть левее и вот оно - 89.

То есть четыре сравнения. А если бы ты шел по массиву с начала, то было бы 10 сравнений. Вот и вся хитрость...

--------------------

Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие

LuckLess

Дата 30.3.2006, 00:17 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 180
Регистрация: 15.9.2004

Репутация: 1
Всего: 1

вот небольшой пример

Код


#include <iostream>
#include <algorithm>
#include <vector>

template<class Iter , class ValType>
Iter my_bin_search(Iter begin , Iter end , ValType val){
    Iter save_end=end;//сохраняем конец.
    --end;
    Iter ret = begin;
    if (val <*begin || val >*end){
        ret = save_end;
    }else{
        while (1){
            if (val >*begin && val < *end){//пока не нашли
                int dist = end - begin;
                if (dist == 1){//не найдено.
                    ret = save_end;
                    break;
                }
                ret = end-(dist/2);//делим пополам
                if (val >= *ret) begin = ret;
                else end = ret;
            }else{//нашли!!
                if (val==*begin)
                    ret = begin;
                else
                    ret = end;
                break;
            }
        }
    }
    return ret;
}
#include <windows.h>

void main(void){
    
    srand(GetTickCount());

    std::vector<int> vec;
    for (int i = 0 ; i < 10 ; ++i)
        vec.push_back(rand());

    std::sort(vec.begin(),vec.end());

    for (int i = 0 ; i < 10 ; ++i)
        std::cout << vec.at(i) << " ";

    std::cout << "\nlookin for :";
    int n;
    std::cin >> n;
    

    typedef std::vector<int>::iterator IT;
    IT it = my_bin_search(vec.begin(),vec.end(),n);

    if (it == vec.end())
        std::cout << "not found";
    else
        std::cout << it - vec.begin() +1;
}

Это сообщение отредактировал(а) LuckLess - 30.3.2006, 00:33

sergejzr

Дата 30.3.2006, 01:03 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 19
Всего: 360

http://sergejzr.jino-net.ru/sergpage/bs/start.htm
smile

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

cardinal

Дата 30.3.2006, 01:04 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 2
Всего: 99

А что это за сайт? У меня аж компер подвис из-за плейера... smile

--------------------

sergejzr

Дата 30.3.2006, 01:06 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: 19
Всего: 360

Это флэш. Визуализация бинарного поиска. Наверно ИЕ должен взять.

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

Voldemar2004

Дата 30.3.2006, 22:35 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1650
Регистрация: 25.12.2004

Репутация: нет
Всего: 23

Так там вся фишка в том, что массив надо сначала упорядочить. smile

Тогда все ясно:

Цитата(cardinal @ 30.3.2006, 00:10

)

У тебя упорядоченный массив с числами
2, 6, 23, 26, 45, 67, 78, 79, 83, 89, 97, 100

Код

int m=VipCount;
do
{
        for(int i=0; i<VipCount-1; i++)
        {
                if(strcmp(f[i].Fam, f[i+1].Fam)>0)
                {
                tVipusknik a = f[i];
                f[i] = f[i+1];
                f[i+1] = a;
                }
        };
m--;
}
while(m>0);

for(int i=0; i<VipCount; i++)
{
 cout<<f[i].Fam<<"\t"<<f[i].Name<<"\t"<<f[i].Otch<<"\t"<<f[i].VUZ<<"\t"<<f[i].Spec<<"\t"<<f[i].GOD;
 if(i/6==0) {cout<<"\n";};
};

--------------------

i_i
(';')
(V)

user posted image

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »