Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
MaxAvatar
0 / 0 / 0
Регистрация: 07.11.2014
Сообщений: 7
1

Бинарный поиск

06.12.2014, 05:21. Просмотров 383. Ответов 3
Метки нет (Все метки)

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <vector>
 
using namespace std;
 
struct translation
{
    string english;
    string russian;
};
 
bool sort_sorter(translation i, translation j){
    return i.english < j.english;
}
 
void search_word(vector<translation>& dictionary)
{
    string search_word;
    cin >> search_word;
    ifstream dict("dict.txt", ifstream::in | ifstream::binary);
    int i = 0, left = 0, right = dictionary.size(), mid = 0;
    while (left <= right)
    {
        mid = left + (right - left) / 2;
        if (int(search_word[i]) < int(dictionary[mid].english[i])) { right = mid - 1; }
        if (int(search_word[i]) > int(dictionary[mid].english[i])) { left = mid + 1; }
        if (int(search_word[i]) == int(dictionary[mid].english[i])) { i++; }
        if ((search_word.size() == i) && (dictionary[mid].english.size() == i)) break;
    }
    cout << dictionary[mid].english << endl;
    dict.close();
}
 
int main()
{
    setlocale(LC_ALL, "Russian");
    translation buffer;
    ifstream dict("dict.txt", ifstream::in | ifstream::binary);
    vector<translation> dictionary;
    while ((!dict.eof()) && (dict.good()))
    {
        getline(dict, buffer.english);
        getline(dict, buffer.russian);
        dictionary.push_back(buffer);
    };
 
    dict.close();
 
    sort(dictionary.begin(), dictionary.end(), sort_sorter);
    ofstream dict1("dict.txt", ofstream::out | ofstream::binary | ofstream::trunc);
    for (int i = 0; i < dictionary.size(); i++)
    {
        dict1 << dictionary[i].english;
        dict1 << endl;
        dict1 << dictionary[i].russian;
        if (i + 1 == dictionary.size()) break;
        dict1 << endl;
    }
    for (int i = 0; i < dictionary.size(); i++)
    {
        cout << dictionary[i].english;
        cout << endl;
        cout << dictionary[i].russian;
        //if (i + 1 == dictionary.size()) break;
        cout << endl;
    }
 
    dict1.close();
 
    search_word(dictionary);
 
    return 0;
}
В функции "void search_word(vector<translation>& dictionary)" всё вроде бы написано нормально, но ищет почему-то криво. Некоторые слова находит, а остальные путает.
Словарь лежит в файле dict.txt и имеет вид:
apple
яблоко
automobile
автомобиль
bedroom
спальня
brother
брат
bus
автобус
car
машина
cat
кот
computer
компьютер
dog
собака
father
папа
house
дом
laptop
ноутбук
mother
мама
notebook
тутрадь
sidewalk
тротуар
telephone
телефон
zebra
зебра
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.12.2014, 05:21
Ответы с готовыми решениями:

Поиск числа в двумерном массиве (бинарный поиск)
Произвожу поиск элемента в массиве двумя способами: линейным(последовательным)...

Бинарный поиск
Найти индекс расположения числа 15 в массиве на 20 элементов и сумму элементов...

Бинарный поиск
Здравствуйте, помогите пожалуйста написать бинарный поиск одного элемента,...

Бинарный поиск
Всем привет! У меня вот тут маленькая проблемка! Помогите исправить, а то сама...

Бинарный поиск
Каким образом выполнить бинарный поиск определнного значения в отсортированном...

3
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4837 / 2482 / 695
Регистрация: 18.10.2014
Сообщений: 4,290
06.12.2014, 08:46 2
Цитата Сообщение от MaxAvatar Посмотреть сообщение
Некоторые слова находит, а остальные путает.
Во-первых, сразу бросается в глаза, что 'right' изначально равно 'dictionary.size()', т.е задумка автора как будто в том, что работать мы будем с дипазоном '[left, right)', т.е. левый край - включается, а правый - исключается. Однако переход 'right = mid - 1' уже этому противоречит. Это исключает из рассмотрения элемент 'mid-1'. Почему так сделано? Или задумка все таки работать с диапазоном '[left, right]'? Но почему тогда начальное значение 'right' - это 'dictionary.size()', а не 'dictionary.size() - 1'?

Во-вторых, а что это у вас вообще за алгоритм поиска такой странный? Я смотрю, вы сравниваете только позицию 'i'. Как только вы наткнулись на искомую букву в позиции 'i' в словаре, вы смело увеличиваете 'i' и продоложаете бинарный поиск по новой позиции 'i'. Это какая-то бессмыслица, которая в таком виде не может работать правильно. При увеличении значения 'i' последовтельность символов в позиции 'i' уже не является отсортированной и делать какой-то бинарный поиск в ней невозможно.

Например, пусть у нас есть отсортированный словарь

[0]: ABA
[1]: BAC
[2]: BBC
[3]: CAB
[4]: СCA
[5]: DAA
[6]: DAB

И пусть мы ищем ССА. На первой же итерации для i=0, left=0, right=7, mid=3 мы видим совпадение первой буквы: C == C. Мы увеличиваем i до 1 и повторяем итерацию для i=1 и тех же значений left, right и mid. Мы видим, что C > A, и выигрывает правый промежуток. Теперь i=1, left=3, right=7, mid=5. Здесь мы снова видим, что C > A, и делаем left=6. Все, приехали. Наше искомое ССA оказалось за пределами промежутка left=6, right=7 и мы его уже никогда не найдем.

Откуда вы взяли этот алгоритм со сравнением по одному символу? (В нем есть что-то остроумное и его, наверное, можно довести до ума, но это отдельная тема.) Почемы вы не используете классическое полное сравнение, которое вы используете в сортировке?
1
MaxAvatar
0 / 0 / 0
Регистрация: 07.11.2014
Сообщений: 7
06.12.2014, 19:34  [ТС] 3
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Во-первых, сразу бросается в глаза, что 'right' изначально равно 'dictionary.size()', т.е задумка автора как будто в том, что работать мы будем с дипазоном '[left, right)', т.е. левый край - включается, а правый - исключается. Однако переход 'right = mid - 1' уже этому противоречит. Это исключает из рассмотрения элемент 'mid-1'. Почему так сделано? Или задумка все таки работать с диапазоном '[left, right]'? Но почему тогда начальное значение 'right' - это 'dictionary.size()', а не 'dictionary.size() - 1'?

Во-вторых, а что это у вас вообще за алгоритм поиска такой странный? Я смотрю, вы сравниваете только позицию 'i'. Как только вы наткнулись на искомую букву в позиции 'i' в словаре, вы смело увеличиваете 'i' и продоложаете бинарный поиск по новой позиции 'i'. Это какая-то бессмыслица, которая в таком виде не может работать правильно. При увеличении значения 'i' последовтельность символов в позиции 'i' уже не является отсортированной и делать какой-то бинарный поиск в ней невозможно.

Например, пусть у нас есть отсортированный словарь

[0]: ABA
[1]: BAC
[2]: BBC
[3]: CAB
[4]: СCA
[5]: DAA
[6]: DAB

И пусть мы ищем ССА. На первой же итерации для i=0, left=0, right=7, mid=3 мы видим совпадение первой буквы: C == C. Мы увеличиваем i до 1 и повторяем итерацию для i=1 и тех же значений left, right и mid. Мы видим, что C > A, и выигрывает правый промежуток. Теперь i=1, left=3, right=7, mid=5. Здесь мы снова видим, что C > A, и делаем left=6. Все, приехали. Наше искомое ССA оказалось за пределами промежутка left=6, right=7 и мы его уже никогда не найдем.

Откуда вы взяли этот алгоритм со сравнением по одному символу? (В нем есть что-то остроумное и его, наверное, можно довести до ума, но это отдельная тема.) Почемы вы не используете классическое полное сравнение, которое вы используете в сортировке?
Почемы вы не используете классическое полное сравнение, которое вы используете в сортировке?
А как можно реализовать полное сравнение? Чтобы определяло, что string больше сравниваемого с ним или меньше
0
TheCalligrapher
С чаем беда...
Эксперт CЭксперт С++
4837 / 2482 / 695
Регистрация: 18.10.2014
Сообщений: 4,290
06.12.2014, 23:52 4
Цитата Сообщение от MaxAvatar Посмотреть сообщение
А как можно реализовать полное сравнение? Чтобы определяло, что string больше сравниваемого с ним или меньше
Полное сравнение для типа std::string уже реализовано через оператор '<'. Вы же сами уже пользуетесь этим самым готовым оператором в вашей функции 'sort_sorter'.

Меня то и удивляет, что несколькими строчками выше вы пользуетесь готовым оператором '<', а здесь вдруг взялись выписывать сравнение вручную каким-то хитрым образом.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.12.2014, 23:52

Бинарный поиск
Что переделать в программе, чтобы она находила первый элемент больше или равный...

Бинарный поиск c++
1) последовательного поиска максимального элемента в одномерном динамическом...

Бинарный поиск
Здравствуйте, не могу понять как составить алгоритм: нужно найти сумму...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru