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

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

Войти
Регистрация
Восстановить пароль
 
Natalii
0 / 0 / 0
Регистрация: 31.03.2012
Сообщений: 9
#1

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

29.11.2013, 21:00. Просмотров 336. Ответов 1
Метки нет (Все метки)

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

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

двоичный поиск - C++
Подскажите, пожалуйста, в вопросе: Какое дополнительное требование к массиву может быть применено при двоичном поиске, что бы определить...

Двоичный поиск - C++
Помогите пожалуйста с двоичным поиском: нужно найти абитуриента с 287 баллами методом двоичного поиска.. #include <iostream.h> ...

Двоичный поиск - C++
Требуется найти в массиве элементы которые повторяются и элементы которые присутствуют единожды. #include <stdafx.h> #define N 10 ...

Двоичный поиск - C++
Добрый день. Помогите найти ошибку в двоичном поиске. Вот код: #include <iostream> #include <conio.h> using namespace std; int...

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

1
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 */
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.11.2013, 19:42
Привет! Вот еще темы с ответами:

Двоичный(бинарный) поиск - C++
Столкнулся с такой проблемой. использую бинарный поиск в упорядоченном массиве чисел для поиска количества повторений нужного мне числа К...

Двоичный (бинарный) поиск - C++
Вот такой вот вопрос: Есть например такой линейный массив 1 1 1 1 2 3 4 5 6 Вводят какое-то число и нужно проверить сколько...

Приближенный двоичный поиск - C++
Доброго времени суток, форумчане. Задача такая: В первой строке входных данных содержатся числа N и K (0 &gt; N,K &gt;100001 ). Во второй...

Нерекурсивный двоичный поиск - C++
необходимо написать на С++ двоичный поиск в рекурсивном варианте. вот пример рекурсивной ф-ции двоичного поиска: int BinSerch(int...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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