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

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

Восстановить пароль Регистрация
 
vladislav23
0 / 0 / 0
Регистрация: 28.04.2013
Сообщений: 24
28.04.2013, 16:53     Бинарный поиск #1
Здравствуйте, помогите пожалуйста написать бинарный поиск одного элемента, текст читается из файла. Лабу сдавать в понедельник а я не знаю как сделать помогите пожалуйста, буду очень благодарен.

Добавлено через 5 часов 42 минуты
...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.04.2013, 16:53     Бинарный поиск
Посмотрите здесь:

C++ бинарный поиск
Бинарный поиск C++
C++ Бинарный поиск
Бинарный поиск C++
Бинарный поиск C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
28.04.2013, 20:22     Бинарный поиск #2
Что такое "элемент текстового файла"?
Строка? Символ?
Бинарный поиск возможен только в случае, если элементы упорядочены. Гарантируется, что элементы на входе упорядочены?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
28.04.2013, 21:35     Бинарный поиск #3
lemegeton, вы правы, но в более общем случае говорят, что бинарный поиск определён на монотонной функции. Просто, в бинарном поиске очень удобно использовать функцию, которая отдельно описывается.
C++
1
2
3
4
5
6
7
8
9
int l = min значение
int r = max значение (эти переменные можно сделать и вещественными)
for (int i = 0; i < n; i++) {
 int mid = (l+r)/2;
 if (g(mid)) // функция g монотонна b и возращает true или false
  l = mid;
 else 
  r = mid;
}
по окончании :
mid - итоговая позиция
g(mid) - найденный элемент
ZaMaZaN4iK
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
28.04.2013, 21:37     Бинарный поиск #4
бинарный поиск применяется только для упорядоченных массивов.ТО есть вы должны счиать данные в массив, отсортировать их, а потом уже искать элемент бинарным поиском(дихотомией).вот сам код дихотомии:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int bin_search(int key,int size)
{
    if(size == 0 || arr[0]>key || arr[size-1]<key)
        return -1;
    int first=0,last=size-1,mid;
    while(first < last)
    {
        mid=first + ((last-first)>>1);
        if(arr[mid] == key)
            return mid;
        else if(arr[mid] > key)
            last=mid-1;
        else
            first=mid+1;
    }
    if(arr[last]==key)
        return last;
    else
        return -1;
}
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
29.04.2013, 00:41     Бинарный поиск #5
Если это строки, можно так.
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <cstring>
#include <iostream>
#include <fstream>
 
template <class ForwardIterator, class T, class Compare>
ForwardIterator lowerBound (ForwardIterator first, ForwardIterator last,
  const T& value, Compare compare) {
  size_t count = last - first;
  while (count > 0) {
    ForwardIterator it = first;
    size_t step = count / 2;
    it += step;
    if (compare(*it, value)) {
      first = ++it;
      count -= step + 1;
    } else {
      count = step;
    }
  }
  return first;
}
 
class SortedStrings {
 public:
  typedef char **Iterator;
  typedef char *const *ConstIterator;
  SortedStrings() : capacity(10), size(0), strings(new char*[capacity]) {}
  virtual ~SortedStrings() {
    clear();
    delete [] strings;
  }
  void clear() {
    for (size_t i = 0; i < size; ++i) {
      delete [] strings[i];
    }
    size = 0;
  }
  size_t getSize() const { return size; }
  ConstIterator insert(const char *string) {
    checkCapacity(1);
    Iterator position = lowerBound(strings, strings + size, string,
      lesserString);
    for (Iterator i = strings + size; i > position; --i) {
      *i = *(i - 1);
    }
    *position = strcpy(new char[strlen(string) + 1], string);
    ++size;
    return position;
  }
  void remove(ConstIterator position) {
    size_t offset = position - strings;
    delete [] strings[offset];
    for (Iterator i = strings + offset; i < end(); ++i) {
      *i = *(i + 1);
    }
    --size;
  }
  ConstIterator begin() { return strings; }
  ConstIterator end() { return strings + size; }
  bool contains(const char *string) {
    Iterator position = lowerBound(strings, strings + size, string,
      lesserString);
    return position != end() && !lesserString(string, *position);
  }
 private:
  static bool lesserString(const char *a, const char *b) {
    return strcmp(a, b) < 0;
  }
  void checkCapacity(int increment) {
    if (capacity < capacity + increment) {
      capacity += increment;
      char **newData = new char*[capacity];
      for (size_t i = 0; i < size; ++i) {
        newData[i] = strings[i];
      }
      delete [] strings;
      strings = newData;
    }
  }
  size_t capacity;
  size_t size;
  char **strings;
};
 
int main(int argc, char *argv[]) {
  SortedStrings s;
  
  std::ifstream input("names.txt");
 
  while (!input.eof()) {
    char buffer[1024];
    input.getline(buffer, sizeof(buffer) - 1);
    if (!input.eof()) {
      s.insert(buffer);
    }
  }
  
  for (SortedStrings::ConstIterator i = s.begin(); i != s.end(); ++i) {
    std::cout << *i << std::endl;
  }
 
  char searchable[] = "Anna Annovna";
  std::cout << "Sorted string list " <<
    (s.contains(searchable) ? "contains '" : "does not contain '") <<
    searchable << "'" << std::endl;
 
  return 0;
}
Yandex
Объявления
29.04.2013, 00:41     Бинарный поиск
Ответ Создать тему
Опции темы

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