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

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

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

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

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

Помогите пожалуйста!!!
Как запрограммировать в рекурсивной форме алгоритм бинарного поиска
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.03.2012, 21:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как запрограммировать в рекурсивной форме алгоритм бинарного поиска (C++):

Реализовать алгоритм бинарного поиска с рекурсией - C++
Реалезовать алгоритм бинарного поиска с помощью рекурсии.

Используя алгоритм бинарного поиска определите - C++
Используя алгоритм бинарного поиска определите , содержит ли ранее упорядоченный массив заданное действительное число. Если содержит ,...

(ищу) Алгоритм построения бинарного дерева поиска - C++
Помогите пожалуйста. Если у кого завалялся алгоритм построения бинарного дерева поиска. Поделитесь. Очень нужно. Желательно что-бы цифры...

Дан массив упорядоченных по возрастанию целых чисел. разработать алгоритм бинарного поиска заданного числа, результат номер искомого числа или 0 если - C++
помогите решить задачу: Дан массив упорядоченных по возрастанию целых чисел. разработать алгоритм бинарного поиска заданного числа,...

Разобраться с рекурсивной функцией обхода бинарного дерева - C++
Люди, помогите разобраться с рекурсивной функцией обхода бинарного дерева. Бьюсь головой об стену, не могу понять как она работает. ...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; void lab () { int s1 = 0; int s2 =...

4
DU
1483 / 1129 / 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;
}
1
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 да? а что это за число позиция или просто число в массиве? или первое вхождение?
0
DU
1483 / 1129 / 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, потому что индексы начинаются от нуля).
1
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, потому что индексы начинаются от нуля).
Спасибо огромное!!!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.03.2012, 21:13
Привет! Вот еще темы с ответами:

Алгоритм рекурсивной процедуры - C++
Нужен простенький алгоритм для рекурсивной процедуры перебора вариантов. Задача такая,например n==3; k==2; Вывод 222 221 212 211 122...

Запрограммировать рекурсивный алгоритм вычисления квадрата - C++
Добрый вечер. Может кто нить помочь.. Запрограммировать рекурсивный алгоритм вычисления квадрата натурального числа, используя...

Алгоритм рекурсивной процедуры генерации перестановок чисел - C++
Нужен простенький алгоритм алгоритм рекурсивной процедуры генерации перестановок чисел от 1 до n... Например n==3 Вывод: 111 ...

Сложность бинарного поиска - C++
Добрый вечер, решал данную задачу: Девочка загадала число от 1 до N. За какое наименьшее количество вопросов вида «Загаданное тобой...


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

Или воспользуйтесь поиском по форуму:
5
Yandex
Объявления
05.03.2012, 21:13
Ответ Создать тему
Опции темы

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