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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Нарек
0 / 0 / 0
Регистрация: 30.05.2013
Сообщений: 8
#1

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

31.05.2013, 18:28. Просмотров 574. Ответов 5
Метки нет (Все метки)

Приветствую друзья программисты.
Нужна ваша неотъемлемая помощь.
В отсортированном одномерном массиве 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++ Реализовать программу, осуществляющую поиск выхода из лабиринта методом поиска с возвратом.
Блочная сортировка массива и поиск заданного элемента C++
Англо-русского словарь методом дерева бинарного поиска C++
C++ Дан массив упорядоченных по возрастанию целых чисел. разработать алгоритм бинарного поиска заданного числа, результат номер искомого числа или 0 если
Поиск элемента в отсортированном массиве методом бинарного дерева C++
В отсортированном одномерном массиве X (100) выполнить поиск заданного элемента последовательным методом C++
C++ В отсортированном одномерном массиве X(100) выполнить поиск за-данного элемента методом однородного бинарного поиска
В отсортированном одномерном массиве выполнить поиск заданного элемента последовательным методом C++
C++ Написать программу бинарного поиска элемента массива равного заданному значению
C++ Поиск строк в файле методами бинарного поиска и перебора
C++ Найти ключ в целочисленном массиве методом бинарного поиска

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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     С++ Выполнить поиск заданного элемента методом однородного бинарного поиска
Ответ Создать тему
Опции темы

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