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

двоичный поиск - C++

Восстановить пароль Регистрация
 
Natalii
0 / 0 / 0
Регистрация: 31.03.2012
Сообщений: 9
29.11.2013, 21:00     двоичный поиск #1
Помогите, пожалуйста, модифицировать программу на рисунке, чтобы для выполнения двоичного поиска в массиве можно было использовать рекурсивную функцию binarySearch. Эта функция должна принимать в качестве параметров целочисленный массив и начальный и конечный индексы. Если ключ поиска найден, возвратить индекс массива; в противном случае возвратить -1.
Миниатюры
двоичный поиск  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.11.2013, 21:00     двоичный поиск
Посмотрите здесь:

C++ Нерекурсивный двоичный поиск
Двоичный поиск C++
Двоичный поиск C++
Двоичный поиск C++
C++ Двоичный поиск в map
двоичный поиск C++
Приближенный двоичный поиск C++
Двоичный поиск C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Natalii
0 / 0 / 0
Регистрация: 31.03.2012
Сообщений: 9
30.11.2013, 19:42  [ТС]     двоичный поиск #2
1 /* Рис. 6.19: fig06_19.c
2 Двоичный поиск в массиве */
3 #include <stdio.h>
4 #define SIZE 15.
5
6 /* прототипы функций */
7 int binarySearch( const int b[], int searchKey,int low,int high );
8 void printHeader( void );
9 void printRow ( const int b[] , int low, int mid, int high ) ;
10
11 /* функция main начинает исполнение программы */
12 int main ()
13 {
14 int a[ SIZE ]; /* создать массив а */
15 int i; /* счетчик для инициализации элементов 0-14 массива а */
16 int key; /* значение для поиска в массиве а */
17 int result; /* переменная для хранения позиции ключа или -1 */
18
19 /* создать данные */
20 for ( i = 0; i < SIZE; i++ ) {
21 a[ i ] = 2 * i;
22 } /* конец for */
23
24 printf( "Enter a number between 0 and 28: " );
25 scanf( "%d", &key );
26
27 printHeader();
28
29 /* поиск ключа в массиве а */
30 result = binarySearch( a, key, 0, SIZE - 1 );
31
32 /* вывести результаты */
33 if ( result != -1 ) {
34 printf( "\n%d found in array element %d\n", key, result );
35 } /* конец if */
36 else {
37 printf( "\n%d not found\n", key );
38 } /* конец else */
39
40 return 0; /* показывает успешное завершение */
41
42 } /* конец main */
43
44 /* функция для двоичного поиска в массиве */
45 int binarySearch( const int b[], int searchKey, int low, int high
46 {
47 int middle; /* переменная для хранения центрального элемента */
48
49 /* цикл, пока нижний индекс меньше верхнего */
50 while ( low <= high ) {
51
52 /* определить центральный элемент текущего подмассива */
53 middle = ( low + high ) / 2;
54
55 /* вывести подмассив, используемый в данной итерации цикла */
56 printRow( b, low, middle, high );
57
58 /* если ключ равен центральному элементу, вернуть middle */
59 if ( searchKey == b[ middle ] ) {
60 return middle;
61 } /* конец if */
62
63 /* если ключ меньше центрального элемента, изменить high */
64 else if ( searchKey < b[ middle ] ) {
65 high = middle - 1; /* найти верхний конец массива */
66 } /* конец else if */
67
68 /* если ключ больше центрального элемента, изменить low */
69 else {
70 low = middle + 1; /* найти нижний конец массива */
71 } /* конец else */
72
73 } /* конец while */
74
75 return -1; /* searchKey не найден */
76
77 } /* конец функции binarySearch */
78
79 /* Напечатать заголовок для вывода */
80 void printHeader( void )
81 {
82 int i; /* счетчик */
83
84 printf( "\nSubscripts:\n" );
85
86 /* вывести заголовок колонки */
87 for ( i = 0; i < SIZE; i++ ) {
88 printf( "%3d ", i ) ;
89 } /* end for */
90
91 printf( "\n" ); /* начать новую строку вывода */
92
93 /* вывести строку символов "-" */
94 for ( i = 1; i <= 4'* SIZE; i++ ) {
95 printf( "-" );
96 } /* конец for */
97
98 printf( "\n" ); /* начать новую строку вывода */
99 } /* конец функции printHeader */
100
101 /* Напечатать одну строку вывода, показывающую
102 обрабатываемую часть массива. */
103 void printRow( const int b[], int low, int mid, int high )
104 {
105 int i; /* счетчик для прохода по массиву b */
106
107 /* цикл по всему массиву */
108 for ( i = 0; i < SIZE; i++ ) {
109
110 /* если вне текущего подмассива, выводить пробелы */
111 if ( i < low || i > high ) {
112 printf( " " ) ;
113 } /* конец if */
114 else if ( i == mid ) { /* выводится центральный элемент */
115 printf( "%3d*", b[ i ] ); /* пометить центральное значение */
116 } /* конец else if */
117 else { /* выводятся остальные элементы подмассива */
118 printf( "%3d ", b[ i ] );
119 } /* конец else */
120
121 } /* конец for */
122
123 printf( "\n" ); /* начать новую строку вывода */
124 } /* конец функции printRow */
Yandex
Объявления
30.11.2013, 19:42     двоичный поиск
Ответ Создать тему
Опции темы

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