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

С++ Выполнить поиск заданного элемента методом однородного бинарного поиска - C++

Восстановить пароль Регистрация
 
Нарек
0 / 0 / 0
Регистрация: 30.05.2013
Сообщений: 8
31.05.2013, 18:28     С++ Выполнить поиск заданного элемента методом однородного бинарного поиска #1
Приветствую друзья программисты.
Нужна ваша неотъемлемая помощь.
В отсортированном одномерном массиве X(100)выполнить поиск заданного элемента методом однородного бинарного поиска.
Буду очень признателен за вашу помощь. Нужно срочно.

Добавлено через 17 часов 59 минут
up!

Добавлено через 6 часов 4 минуты
up!

Добавлено через 2 часа 35 минут
up!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
31.05.2013, 18:28     С++ Выполнить поиск заданного элемента методом однородного бинарного поиска
Посмотрите здесь:

Англо-русского словарь методом дерева бинарного поиска C++
C++ Дан массив упорядоченных по возрастанию целых чисел. разработать алгоритм бинарного поиска заданного числа, результат номер искомого числа или 0 если
Поиск элемента в отсортированном массиве методом бинарного дерева C++
В отсортированном одномерном массиве X (100) выполнить поиск заданного элемента последовательным методом C++
C++ В отсортированном одномерном массиве X(100) выполнить поиск за-данного элемента методом однородного бинарного поиска
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
drdrink
39 / 39 / 1
Регистрация: 13.05.2013
Сообщений: 103
31.05.2013, 21:14     С++ Выполнить поиск заданного элемента методом однородного бинарного поиска #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int bin_search(int *a, int x, int n)  {
        int i = 0, k, c = n - 1;
        k = (i + c)/2 + 1;
        while(i <= c)  {
                if(a[k] == x) 
                        return k;
                else if(a[k] < x) 
                        i = k + 1;
                else
                        c = k - 1;
                k = (i + c)/2;
        }
        if(a[k] == x) 
                return k;
        else 
                return -1;
}
Возвращает номер элемента в масиве, если не найден то -1
Нарек
0 / 0 / 0
Регистрация: 30.05.2013
Сообщений: 8
01.06.2013, 16:15  [ТС]     С++ Выполнить поиск заданного элемента методом однородного бинарного поиска #3
ты уверен что данная программа верная? т.к. у меня есть другой вариант
drdrink
39 / 39 / 1
Регистрация: 13.05.2013
Сообщений: 103
01.06.2013, 21:53     С++ Выполнить поиск заданного элемента методом однородного бинарного поиска #4
Нарек, ну это обычный бинарный поиск, делал ещё на первом курсе, и всё работает=)
Нарек
0 / 0 / 0
Регистрация: 30.05.2013
Сообщений: 8
02.06.2013, 08:11  [ТС]     С++ Выполнить поиск заданного элемента методом однородного бинарного поиска #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
 #include <iostream.h>
 #include <locale.h>
int main() {
    setlocale(LC_ALL,"rus");
  const int n = 100;
  int X[n] = {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},k=0;
  cout << "Массив:\n ";
  for(int i = 0; i < n; ++i){if(k==10){cout<<endl<<endl;k=0;}
    cout << X[i] << ' ';k++; }
  
  int average = 0, first = 0, last = n - 1, value;
  
  cout << "\nВведите число: ";
  cin >> value;
  
  while(first < last) {
    average = first + (last - first) / 2;
    if(value <= X[average])
      last = average;
    else
      first++;
  }
  
  if(value == X[last])
    cout << "Индекс числа в массиве: " << last <<endl;
  else
    cout << "Не найдено!" <<endl;
  
  system("pause");
}
вот то что есть у меня
drdrink
39 / 39 / 1
Регистрация: 13.05.2013
Сообщений: 103
02.06.2013, 10:44     С++ Выполнить поиск заданного элемента методом однородного бинарного поиска #6
Нарек, ну это практически то же самое, суть бинарного поиска заключается в том, что мы сначала делим наш массив на 2 и поскольку этот поиск работает только в упорядоченном массиве по возрастанию, то мы сравниваем значение которое нам найти сначала со срединным элементом, если мы нашли то выход, либо он может быть больше или меньше, если больше то идём в правую часть(на которые мы разбили), если меньше, то идём в левую часть, далее, в зависимости от того какую мы выбрали часть, делим её опять на 2 половинки , и делаем всё то же самое, ну в конце концов мы найдём наш элемент дибо скажем что такового здесь нет=)

Добавлено через 1 минуту
Цитата Сообщение от Нарек Посмотреть сообщение
average = first + (last - first) / 2;
это тоже самое что и:
C++
1
 average = (first + last)/2;
Yandex
Объявления
02.06.2013, 10:44     С++ Выполнить поиск заданного элемента методом однородного бинарного поиска
Ответ Создать тему
Опции темы

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