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

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

Войти
Регистрация
Восстановить пароль
 
Fox01
3 / 3 / 0
Регистрация: 04.03.2012
Сообщений: 55
#1

Как запрограммировать в рекурсивной форме алгоритм бинарного поиска - C++

04.03.2012, 21:55. Просмотров 797. Ответов 4
Метки нет (Все метки)

Помогите пожалуйста!!!
Как запрограммировать в рекурсивной форме алгоритм бинарного поиска
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.03.2012, 21:55     Как запрограммировать в рекурсивной форме алгоритм бинарного поиска
Посмотрите здесь:

C++ (ищу) Алгоритм построения бинарного дерева поиска
Реализовать алгоритм бинарного поиска с рекурсией C++
C++ Дерево бинарного поиска
Запрограммировать рекурсивный алгоритм вычисления квадрата C++
Как сделать алгоритм поиска в вложенном классе? C++
C++ Дан массив упорядоченных по возрастанию целых чисел. разработать алгоритм бинарного поиска заданного числа, результат номер искомого числа или 0 если
Используя алгоритм бинарного поиска определите C++
C++ Разобраться с рекурсивной функцией обхода бинарного дерева
Алгоритм рекурсивной процедуры C++
C++ Алгоритм рекурсивной процедуры генерации перестановок чисел
Реализация бинарного поиска C++
C++ Сложность бинарного поиска

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DU
1479 / 1055 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
04.03.2012, 23:08     Как запрограммировать в рекурсивной форме алгоритм бинарного поиска #2
вот например такой поиск в сортированном массиве:
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
#include <iostream>
 
const int* FindFirstElem(const int* arr, unsigned size, int value)
{
  if (arr == 0 || size == 0)
    return 0;
 
  if (size == 1)
    return arr[0] == value ? arr : 0;
 
  const unsigned halfArrSize = size / 2;
 
  if (arr[halfArrSize - 1] < value)
    return FindFirstElem(arr + halfArrSize, size - halfArrSize, value);
 
  return FindFirstElem(arr, halfArrSize, value);
}
 
int FindFirstIndex(const int* arr, unsigned size, int value)
{
  const int* result = FindFirstElem(arr, size, value);
  return result == 0 ? -1 : static_cast<int>(result - arr);
}
 
int main()
{
  const int arr[] = {0, 1, 2, 3, 4, 5, 5, 6, 7};
  const int searchValue = 5;
  const int* result = FindFirstElem(arr, sizeof(arr) / sizeof(*arr), searchValue);
  if (result != 0)
  {
    std::cout << "The '" << searchValue << "' is found." << std::endl;
    std::cout << "First value index = " << result - arr << std::endl;
  }
  else
  {
    std::cout << "The '" << searchValue << "' is not found." << std::endl;
  }
 
  const int index = FindFirstIndex(arr, sizeof(arr) / sizeof(*arr), searchValue);
  std::cout << "Index = " << index << std::endl;
 
  return 0;
}
Fox01
3 / 3 / 0
Регистрация: 04.03.2012
Сообщений: 55
05.03.2012, 20:15  [ТС]     Как запрограммировать в рекурсивной форме алгоритм бинарного поиска #3
Цитата Сообщение от DU Посмотреть сообщение
вот например такой поиск в сортированном массиве:
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
#include <iostream>
 
const int* FindFirstElem(const int* arr, unsigned size, int value)
{
  if (arr == 0 || size == 0)
    return 0;
 
  if (size == 1)
    return arr[0] == value ? arr : 0;
 
  const unsigned halfArrSize = size / 2;
 
  if (arr[halfArrSize - 1] < value)
    return FindFirstElem(arr + halfArrSize, size - halfArrSize, value);
 
  return FindFirstElem(arr, halfArrSize, value);
}
 
int FindFirstIndex(const int* arr, unsigned size, int value)
{
  const int* result = FindFirstElem(arr, size, value);
  return result == 0 ? -1 : static_cast<int>(result - arr);
}
 
int main()
{
  const int arr[] = {0, 1, 2, 3, 4, 5, 5, 6, 7};
  const int searchValue = 5;
  const int* result = FindFirstElem(arr, sizeof(arr) / sizeof(*arr), searchValue);
  if (result != 0)
  {
    std::cout << "The '" << searchValue << "' is found." << std::endl;
    std::cout << "First value index = " << result - arr << std::endl;
  }
  else
  {
    std::cout << "The '" << searchValue << "' is not found." << std::endl;
  }
 
  const int index = FindFirstIndex(arr, sizeof(arr) / sizeof(*arr), searchValue);
  std::cout << "Index = " << index << std::endl;
 
  return 0;
}
Если Вас не затруднит - не могли бы Вы немного пояснить мне код программы - что есть что - а то я запуталась... задаю массив - после задаю число - в примере это 5 да? а что это за число позиция или просто число в массиве? или первое вхождение?
DU
1479 / 1055 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
05.03.2012, 21:00     Как запрограммировать в рекурсивной форме алгоритм бинарного поиска #4
searchValue - это то, что ищется в массиве.

вот при такой комбинации
C++
1
2
  const int arr[] = {0, 0, 0, 0, 2, 2, 2, 2, 4, 5};
  const int searchValue = 2;
вернется первое вхождение двойки. это пятый элемент по порядку (индекс у него будет 4, потому что индексы начинаются от нуля).
Fox01
3 / 3 / 0
Регистрация: 04.03.2012
Сообщений: 55
05.03.2012, 21:13  [ТС]     Как запрограммировать в рекурсивной форме алгоритм бинарного поиска #5
Цитата Сообщение от DU Посмотреть сообщение
searchValue - это то, что ищется в массиве.

вот при такой комбинации
C++
1
2
  const int arr[] = {0, 0, 0, 0, 2, 2, 2, 2, 4, 5};
  const int searchValue = 2;
вернется первое вхождение двойки. это пятый элемент по порядку (индекс у него будет 4, потому что индексы начинаются от нуля).
Спасибо огромное!!!
Yandex
Объявления
05.03.2012, 21:13     Как запрограммировать в рекурсивной форме алгоритм бинарного поиска
Ответ Создать тему
Опции темы

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