1 / 1 / 1
Регистрация: 09.10.2014
Сообщений: 79
1

Поиск числа в двумерном массиве (бинарный поиск)

12.04.2015, 20:30. Показов 14349. Ответов 8
Метки нет (Все метки)

Произвожу поиск элемента в массиве двумя способами: линейным(последовательным) поиском и бинарным(двоичным). Первый работает на ура. Второй корректно показывает есть элемент в массиве или нет. Но количество совпадений всегда по нулям. Не пойму куда счетчик подсчета совпадений правильно вставить. Приложил скрин работы.
Поиск числа в двумерном массиве (бинарный поиск)


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
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include <iostream>
#include <string>
#include <ctime>
 
using namespace std;
bool f;
 
void output_matrix(int ** matrix, int rows, int columns)
{
    for (int i = 0; i < rows; ++i)
    {
        for (int j = 0; j < columns; ++j)
        {
            cout << matrix[i][j] << ' ';
        }
        cout << endl;
    }
}
 
//Копирование одной матрицы в другую.
//Первый параметр - матрица назначения, второй - матрица-источник
void copy_matrix(int ** dest_matrix, int ** source_matrix, int rows, int columns)
{
    for (int i = 0; i < rows; ++i)
    for (int j = 0; j < columns; ++j)
        dest_matrix[i][j] = source_matrix[i][j];
}
 
void LineSearch(int **arr, int rows, int cols, int key)
{
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; ++j)
        if (arr[i][j] == key)
        {
            cout << "Найденный элемент находится на " << i + 1 << " строке, в " << j + 1 << " столбце." << endl;
            f = true;
        }
    }
}
 
void insertSort(int * arr, int arr_size)
{
    int tmp;
    for (int i = 1, j; i < arr_size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = arr[i]; //Запоминаем проверяемый элемент (тот, для которого будем искать новую позицию)
        for (j = i - 1; j >= 0; j -= 1) // цикл поиска позиции вставки в готовой последовательности
        {
            //Цикл идет в обратном направлении (от i к 0)
            //в цикле сдвигаем элементы "направо", пока не найдем позицию вставки
            if (arr[j] > tmp) //Если данный элемент меньше проверяемого, то
            {
                arr[j + 1] = arr[j]; //Сдвигаем данный элемент вправо
                //  ++swap_count;
            }
            else
            {
                break;
            }
        }//++swap_count;
        //Когда цикл завершен - позиция найдена
        if ((j + 1) != i)
        {
 
            arr[j + 1] = tmp; // вставить проверяемый элемент в найденную позицию
        }
    }
}
 
int BinarSearch(int **arr, int rows, int cols, int key, int count)
{
//  int count = 0;
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; ++j)
        {
            int center = 0, left = 0;
            int right = cols - 1;
            while (left <= right)
            {
                center = left + (right - left) / 2;
                if (key<arr[i][center])
                {
                    right = center - 1;
                    count++;
                }
                else if (key>arr[i][center])
                {
                    left = center + 1;
                    count++;
                }
                else return center;
            }
        }
    }
    return -1;
}
 
int main()
{
    srand(time(NULL));
    setlocale(LC_ALL, "");
    string insert_rows, insert_columns, insert_key;
    int key, rows, columns, count = 0;
    int i = 0;
 
    cout << "Введите кол-во строк матрицы: ";
    getline(cin, insert_rows);
    while (!insert_rows[0])
    {
        cout << "Вы ввели Enter" << endl;
        getline(cin, insert_rows);
    }
    rows = stoi(insert_rows);
 
    cout << "Введите кол-во стобцов матрицы: ";
    getline(cin, insert_columns);
    while (!insert_columns[0])
    {
        cout << "Вы ввели Enter" << endl;
        getline(cin, insert_columns);
    }
    columns = stoi(insert_columns);
 
    int ** matrix = new int*[rows];
    int ** sorted_matrix = new int*[rows];
    //Динамическое создание двумерного массива
    for (int count = 0; count < rows; count++)
    {
        matrix[count] = new int[columns];
        sorted_matrix[i] = new int[columns];
    }
 
    //Заполнение и вывод массива 
    for (int i = 0; i < rows; ++i) //Проходим по всем строкам
    {
        matrix[i] = new int[columns];//Выделяем память под элементы строки
        sorted_matrix[i] = new int[columns];//Выделяем память под элементы строки
        for (int j = 0; j < columns; ++j) //проходим по элементам строки
        {
            matrix[i][j] = rand() % 10; //Генерируем число в интервале [10,99]
        }
    }
    cout << "Исходная матрица:\n";
    output_matrix(matrix, rows, columns);
    cout << "Искомый элемент: ";
    getline(cin, insert_key);
    while (!insert_key[0])
    {
        cout << "Вы ввели Enter" << endl;
        getline(cin, insert_key);
    }
    key = stoi(insert_key);
    LineSearch(&matrix[i], rows, columns, key);
    if (!f)
    {
        cout << "Элемент не найден" << endl;
    }
 
    //////////////////////////////////////////////
    //////СОРТИРОВКА ДЛЯ БИНАРНОГО ПОИСКА/////////
    //////////////////////////////////////////////
 
    copy_matrix(sorted_matrix, matrix, rows, columns);
 
    for (int i = 0; i < rows; ++i)
    {
        insertSort(sorted_matrix[i], columns);
    }
    output_matrix(sorted_matrix, rows, columns);
    cout << "Искомый элемент: ";
    cin >> key;
 
    if (BinarSearch(&sorted_matrix[i], rows, columns, key, count) != -1)
    {
        cout << "Искомый элемент есть в массиве" << endl;
    cout << "Количество совпадений = " << count;
    }
    else
        cout << "Искомый элемент не найден" << endl;
 
    //Удаление двумерного динамического массива
    for (int count = 0; count < rows; count++)
    {
        delete[] matrix[count];
    }
    delete[] matrix;
    return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.04.2015, 20:30
Ответы с готовыми решениями:

Двоичный (бинарный) поиск элемента в двумерном массиве
Доброго времени суток. есть вот такое задание: Написать функцию, реализующую алгоритм бинарного...

Бинарный поиск числа в массиве
Здравствуйте имеется программка в которую через клаву вводишь определенное кол-во чисел(кол-во...

Бинарный поиск числа в массиве
Дан упорядоченный массив чисел от 0 до 100. Необходимо выполнить бинарный поиск числа 25. Как его...

Бинарный поиск числа в упорядоченном массиве
В упорядоченном массиве надо найти число. Программа должна выполняться с рекурсией

8
467 / 370 / 176
Регистрация: 08.04.2013
Сообщений: 1,596
12.04.2015, 20:52 2
объяви count как глобальная переменная, то есть int count=0; до int main() для int BinarSearch или используй другую, т.к ты её еще для чего то исползуешь
0
1 / 1 / 1
Регистрация: 09.10.2014
Сообщений: 79
12.04.2015, 21:17  [ТС] 3
не помогло

Добавлено через 3 минуты
Понял проблему, но не знаю решения. Поиск находит элемент и сразу выходит из функции, он даже не ищет совпадения. В данном коде программы совпадение всегда равно одному, если искомый элемент есть в массиве. Но как заставить искать совпадения?!
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
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <iostream>
#include <string>
#include <ctime>
 
using namespace std;
bool f;
 
void output_matrix(int ** matrix, int rows, int columns)
{
    for (int i = 0; i < rows; ++i)
    {
        for (int j = 0; j < columns; ++j)
        {
            cout << matrix[i][j] << ' ';
        }
        cout << endl;
    }
}
 
//Копирование одной матрицы в другую.
//Первый параметр - матрица назначения, второй - матрица-источник
void copy_matrix(int ** dest_matrix, int ** source_matrix, int rows, int columns)
{
    for (int i = 0; i < rows; ++i)
    for (int j = 0; j < columns; ++j)
        dest_matrix[i][j] = source_matrix[i][j];
}
 
void LineSearch(int **arr, int rows, int cols, int key)
{
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; ++j)
        if (arr[i][j] == key)
        {
            cout << "Найденный элемент находится на " << i + 1 << " строке, в " << j + 1 << " столбце." << endl;
            f = true;
        }
    }
}
 
void insertSort(int * arr, int arr_size)
{
    int tmp;
    for (int i = 1, j; i < arr_size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = arr[i]; //Запоминаем проверяемый элемент (тот, для которого будем искать новую позицию)
        for (j = i - 1; j >= 0; j -= 1) // цикл поиска позиции вставки в готовой последовательности
        {
            //Цикл идет в обратном направлении (от i к 0)
            //в цикле сдвигаем элементы "направо", пока не найдем позицию вставки
            if (arr[j] > tmp) //Если данный элемент меньше проверяемого, то
            {
                arr[j + 1] = arr[j]; //Сдвигаем данный элемент вправо
                //  ++swap_count;
            }
            else
            {
                break;
            }
        }//++swap_count;
        //Когда цикл завершен - позиция найдена
        if ((j + 1) != i)
        {
 
            arr[j + 1] = tmp; // вставить проверяемый элемент в найденную позицию
        }
    }
}
 
int BinarSearch(int **arr, int rows, int cols, int key, int &number)
{
//  int count = 0;
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; ++j)
        {
            int center = 0, left = 0;
            int right = cols - 1;
            while (left <= right)
            {
                center = left + (right - left) / 2;
                if (key<arr[i][center])
                {
                    right = center - 1;
                }
                else if (key>arr[i][center])
                {
                    left = center + 1;
                }
                else {
                    number++;
                    return center;
                }
            }
        }
    }
    return -1;
}
 
int main()
{
    srand(time(NULL));
    setlocale(LC_ALL, "");
    string insert_rows, insert_columns, insert_key;
    int key, rows, columns, number=0, count = 0;
    int i = 0;
 
    cout << "Введите кол-во строк матрицы: ";
    getline(cin, insert_rows);
    while (!insert_rows[0])
    {
        cout << "Вы ввели Enter" << endl;
        getline(cin, insert_rows);
    }
    rows = stoi(insert_rows);
 
    cout << "Введите кол-во стобцов матрицы: ";
    getline(cin, insert_columns);
    while (!insert_columns[0])
    {
        cout << "Вы ввели Enter" << endl;
        getline(cin, insert_columns);
    }
    columns = stoi(insert_columns);
 
    int ** matrix = new int*[rows];
    int ** sorted_matrix = new int*[rows];
    //Динамическое создание двумерного массива
    for (int count = 0; count < rows; count++)
    {
        matrix[count] = new int[columns];
        sorted_matrix[i] = new int[columns];
    }
 
    //Заполнение и вывод массива 
    for (int i = 0; i < rows; ++i) //Проходим по всем строкам
    {
        matrix[i] = new int[columns];//Выделяем память под элементы строки
        sorted_matrix[i] = new int[columns];//Выделяем память под элементы строки
        for (int j = 0; j < columns; ++j) //проходим по элементам строки
        {
            matrix[i][j] = rand() % 10; //Генерируем число в интервале [10,99]
        }
    }
    cout << "Исходная матрица:\n";
    output_matrix(matrix, rows, columns);
    cout << "Искомый элемент: ";
    getline(cin, insert_key);
    while (!insert_key[0])
    {
        cout << "Вы ввели Enter" << endl;
        getline(cin, insert_key);
    }
    key = stoi(insert_key);
    LineSearch(&matrix[i], rows, columns, key);
    if (!f)
    {
        cout << "Элемент не найден" << endl;
    }
 
    //////////////////////////////////////////////
    //////СОРТИРОВКА ДЛЯ БИНАРНОГО ПОИСКА/////////
    //////////////////////////////////////////////
 
    copy_matrix(sorted_matrix, matrix, rows, columns);
 
    for (int i = 0; i < rows; ++i)
    {
        insertSort(sorted_matrix[i], columns);
    }
    output_matrix(sorted_matrix, rows, columns);
    cout << "Искомый элемент: ";
    cin >> key;
 
    if (BinarSearch(&sorted_matrix[i], rows, columns, key, number) != -1)
    {
        cout << "Искомый элемент есть в массиве" << endl;
    cout << "Количество совпадений = " << number << endl;
    }
    else
        cout << "Искомый элемент не найден" << endl;
 
    //Удаление двумерного динамического массива
    for (int count = 0; count < rows; count++)
    {
        delete[] matrix[count];
    }
    delete[] matrix;
    return 0;
}
0
467 / 370 / 176
Регистрация: 08.04.2013
Сообщений: 1,596
12.04.2015, 21:31 4
Думаю для поиска и подсчета элементов в массиве не тот подход. Бинарный - способ быстро найти первый искомый элемент в отсортированном массиве, достаточно большом. А дальше искать и считать другим способом
0
1 / 1 / 1
Регистрация: 09.10.2014
Сообщений: 79
12.04.2015, 21:54  [ТС] 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
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <iostream>
#include <string>
#include <ctime>
 
using namespace std;
bool f;
 
void output_matrix(int ** matrix, int rows, int columns)
{
    for (int i = 0; i < rows; ++i)
    {
        for (int j = 0; j < columns; ++j)
        {
            cout << matrix[i][j] << ' ';
        }
        cout << endl;
    }
}
 
//Копирование одной матрицы в другую.
//Первый параметр - матрица назначения, второй - матрица-источник
void copy_matrix(int ** dest_matrix, int ** source_matrix, int rows, int columns)
{
    for (int i = 0; i < rows; ++i)
    for (int j = 0; j < columns; ++j)
        dest_matrix[i][j] = source_matrix[i][j];
}
 
void LineSearch(int **arr, int rows, int cols, int key)
{
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; ++j)
        if (arr[i][j] == key)
        {
            cout << "Найденный элемент находится на " << i + 1 << " строке, в " << j + 1 << " столбце." << endl;
            f = true;
        }
    }
}
 
void insertSort(int * arr, int arr_size)
{
    int tmp;
    for (int i = 1, j; i < arr_size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = arr[i]; //Запоминаем проверяемый элемент (тот, для которого будем искать новую позицию)
        for (j = i - 1; j >= 0; j -= 1) // цикл поиска позиции вставки в готовой последовательности
        {
            //Цикл идет в обратном направлении (от i к 0)
            //в цикле сдвигаем элементы "направо", пока не найдем позицию вставки
            if (arr[j] > tmp) //Если данный элемент меньше проверяемого, то
            {
                arr[j + 1] = arr[j]; //Сдвигаем данный элемент вправо
                //  ++swap_count;
            }
            else
            {
                break;
            }
        }//++swap_count;
        //Когда цикл завершен - позиция найдена
        if ((j + 1) != i)
        {
 
            arr[j + 1] = tmp; // вставить проверяемый элемент в найденную позицию
        }
    }
}
 
int BinarSearch(int **arr, int rows, int cols, int key, int &number)
{
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; ++j)
        {
            int center = 0, left = 0;
            int right = cols - 1;
            do
            {
                center = left + (right - left) / 2;
                if (arr[i][center] == key)
                {
                    int number = 1;
                    for (int z = center - 1; z >= left && arr[i][z] == key; i--)
                        ++number;
                    for (int z = center + 1; i <= right && arr[i][z] == key; i++)
                        ++number;
                    return number;
                }
                else if (key < arr[i][center])
                    right = center - 1;
                else
                    left = center + 1;
            } while (left <= right);
        }
    }
    return 0;
}
 
int main()
{
    srand(time(NULL));
    setlocale(LC_ALL, "");
    string insert_rows, insert_columns, insert_key;
    int key, rows, columns, number=0, count = 0;
    int i = 0;
 
    cout << "Введите кол-во строк матрицы: ";
    getline(cin, insert_rows);
    while (!insert_rows[0])
    {
        cout << "Вы ввели Enter" << endl;
        getline(cin, insert_rows);
    }
    rows = stoi(insert_rows);
 
    cout << "Введите кол-во стобцов матрицы: ";
    getline(cin, insert_columns);
    while (!insert_columns[0])
    {
        cout << "Вы ввели Enter" << endl;
        getline(cin, insert_columns);
    }
    columns = stoi(insert_columns);
 
    int ** matrix = new int*[rows];
    int ** sorted_matrix = new int*[rows];
    //Динамическое создание двумерного массива
    for (int count = 0; count < rows; count++)
    {
        matrix[count] = new int[columns];
        sorted_matrix[i] = new int[columns];
    }
 
    //Заполнение и вывод массива 
    for (int i = 0; i < rows; ++i) //Проходим по всем строкам
    {
        matrix[i] = new int[columns];//Выделяем память под элементы строки
        sorted_matrix[i] = new int[columns];//Выделяем память под элементы строки
        for (int j = 0; j < columns; ++j) //проходим по элементам строки
        {
            matrix[i][j] = rand() % 10; //Генерируем число в интервале [10,99]
        }
    }
    cout << "Исходная матрица:\n";
    output_matrix(matrix, rows, columns);
    cout << "Искомый элемент: ";
    getline(cin, insert_key);
    while (!insert_key[0])
    {
        cout << "Вы ввели Enter" << endl;
        getline(cin, insert_key);
    }
    key = stoi(insert_key);
    LineSearch(&matrix[i], rows, columns, key);
    if (!f)
    {
        cout << "Элемент не найден" << endl;
    }
 
    //////////////////////////////////////////////
    //////СОРТИРОВКА ДЛЯ БИНАРНОГО ПОИСКА/////////
    //////////////////////////////////////////////
 
    copy_matrix(sorted_matrix, matrix, rows, columns);
 
    for (int i = 0; i < rows; ++i)
    {
        insertSort(sorted_matrix[i], columns);
    }
    output_matrix(sorted_matrix, rows, columns);
    cout << "Искомый элемент: ";
    cin >> key;
 
    if (BinarSearch(&sorted_matrix[i], rows, columns, key, number) != -1)
    {
        cout << "Искомый элемент есть в массиве" << endl;
    cout << "Количество совпадений = " << number << endl;
    }
    else
        cout << "Искомый элемент не найден" << endl;
 
    //Удаление двумерного динамического массива
    for (int count = 0; count < rows; count++)
    {
        delete[] matrix[count];
    }
    delete[] matrix;
    return 0;
}
0
467 / 370 / 176
Регистрация: 08.04.2013
Сообщений: 1,596
13.04.2015, 18:21 6
Вот поработал, но срабатывает бинарный поиск почему то не всегда. Иногда пропускает, иногда срабатывает правильно. Подсчет по строке когда больше одного совпадения пока не реализован.
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
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#include <iostream>
#include <string>
#include <ctime>
#include <windows.h>
 
using namespace std;
char *Rus(char *str)
{
    static char s[1024];
    CharToOem(str, s);
    return s;
}
bool f;
void output_matrix(int ** matrix, int rows, int columns)
{
    for (int i = 0; i < rows; ++i)
    {
        for (int j = 0; j < columns; ++j)
        {
            cout << matrix[i][j] << ' ';
        }
        cout << endl;
    }
}
 
//Копирование одной матрицы в другую.
//Первый параметр - матрица назначения, второй - матрица-источник
void copy_matrix(int ** dest_matrix, int ** source_matrix, int rows, int columns)
{
    for (int i = 0; i < rows; ++i)
    for (int j = 0; j < columns; ++j)
        dest_matrix[i][j] = source_matrix[i][j];
}
 
void LineSearch(int **arr, int rows, int cols, int key)
{
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; ++j)
        if (arr[i][j] == key)
        {
            cout << Rus( "Найденный элемент находится на ") << i + 1 ;
            cout << Rus(" строке, в ") << j + 1;
            cout << Rus(" столбце.") << endl;
            f = true;
        }
    }
}
 
void insertSort(int * arr, int arr_size)
{
    int tmp;
    for (int i = 1, j; i < arr_size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = arr[i]; //Запоминаем проверяемый элемент (тот, для которого будем искать новую позицию)
        for (j = i - 1; j >= 0; j -= 1) // цикл поиска позиции вставки в готовой последовательности
        {
            //Цикл идет в обратном направлении (от i к 0)
            //в цикле сдвигаем элементы "направо", пока не найдем позицию вставки
            if (arr[j] > tmp) //Если данный элемент меньше проверяемого, то
            {
                arr[j + 1] = arr[j]; //Сдвигаем данный элемент вправо
                //  ++swap_count;
            }
            else
            {
                break;
            }
        }//++swap_count;
        //Когда цикл завершен - позиция найдена
        if ((j + 1) != i)
        {
 
            arr[j + 1] = tmp; // вставить проверяемый элемент в найденную позицию
        }
    }
}
 
int BinarSearch(int **arr, int rows, int cols, int key, int* inum)
{
int j=0;
  for (int i=0; i<rows; ++i) {
 
    int left=0, right=cols, mid;
    while (left<=right)
    {
    mid=left+(right-left)/2;
    if (key<arr[i][mid]) right=mid-1;
    else if (key>arr[i][mid]) left=mid+1;
    else {
        *inum=++j;  cout <<"j->"<<mid;cout <<"i-"<<i; goto stop;
    }
     cout<<"Nenasel";
     goto stop;
    }
stop:;  
}
 
//return 0;
}
 
 
int main()
{
    srand(time(NULL));
    setlocale(LC_ALL, "");
    string insert_rows, insert_columns, insert_key;
    int key, rows, columns, number=0, count = 0;
    int i = 0;
    int* inum=&number;
     
    cout << Rus("Введите кол-во строк матрицы: ");
    getline(cin, insert_rows);
    while (!insert_rows[0])
    {
        cout << Rus("Вы ввели Enter" )<< endl;
        getline(cin, insert_rows);
    }
    rows = atoi(insert_rows.c_str());
 
    cout << Rus("Введите кол-во стобцов матрицы: ");
    getline(cin, insert_columns);
    while (!insert_columns[0])
    {
        cout << Rus("Вы ввели Enter") << endl;
        getline(cin, insert_columns);
    }
   // columns = stoi(insert_columns);
   columns = atoi(insert_rows.c_str());
 
    int ** matrix = new int*[rows];
    int ** sorted_matrix = new int*[rows];
    //Динамическое создание двумерного массива
    for (int count = 0; count < rows; count++)
    {
        matrix[count] = new int[columns];
        sorted_matrix[i] = new int[columns];
    }
 
    //Заполнение и вывод массива 
    for (int i = 0; i < rows; ++i) //Проходим по всем строкам
    {
        matrix[i] = new int[columns];//Выделяем память под элементы строки
        sorted_matrix[i] = new int[columns];//Выделяем память под элементы строки
        for (int j = 0; j < columns; ++j) //проходим по элементам строки
        {
            matrix[i][j] = rand() % 10; //Генерируем число в интервале [10,99]
        }
    }
    cout << Rus("Исходная матрица:\n");
    output_matrix(matrix, rows, columns);
    cout << Rus( "Искомый элемент: ");
    getline(cin, insert_key);
    while (!insert_key[0])
    {
        cout << "Вы ввели Enter" << endl;
        getline(cin, insert_key);
    }
   // key = stoi(insert_key);
      key = atoi(insert_key.c_str());
    LineSearch(&matrix[i], rows, columns, key);
    if (!f)
    {
        cout << "Элемент не найден" << endl;
    }
 
    //////////////////////////////////////////////
    //////СОРТИРОВКА ДЛЯ БИНАРНОГО ПОИСКА/////////
    //////////////////////////////////////////////
 
    copy_matrix(sorted_matrix, matrix, rows, columns);
 
    for (int i = 0; i < rows; ++i)
    {
        insertSort(sorted_matrix[i], columns);
    }
    output_matrix(sorted_matrix, rows, columns);
    cout << Rus("Искомый элемент: ");
   // cin >> key;
 
    BinarSearch(sorted_matrix, rows, columns, key, &number) ;
//}
    {
        cout << Rus("Искомый элемент есть в массиве") << endl;
    cout << Rus("Количество совпадений = ") << number << endl;
    }
  //  else
        cout << "Искомый элемент не найден" << endl;
 
    //Удаление двумерного динамического массива
    for (int count = 0; count < rows; count++)
    {
        delete[] matrix[count];
    }
    delete[] matrix;
    return 0;
}
Добавлено через 2 часа 28 минут
с бинарным поиском из вики работает корректно
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
45
46
47
48
49
50
51
int BinarSearch(int **arr, int rows, int cols, int key, int* inum)
{
int j=0;
  for (int i=0; i<rows; i++) {
        /* Номер первого элемента в массиве */
    int first = 0;
    /* Номер элемента в массиве, СЛЕДУЮЩЕГО ЗА последним */
    int last = cols;
    int mid;
    /* Если просматриваемый участок непустой, first < last */
    while (first < last) {
        /* ВНИМАНИЕ! В отличие от более простого (first + last) / 2,
         * этот код устойчив к переполнениям.
         *
         * Если first и last знаковые, возможен код:
         * ((unsigned)first + (unsigned)last) >> 1.
         * Соотвественно в Java: (first + last) >>> 1.
         */
         mid = first + (last - first) / 2;
 
        if (key <= arr[i][mid])
            last = mid;
        else
            first = mid + 1;
    }
 
    /* Если условный оператор if (n == 0) и т.д. в начале опущен -
     * значит, тут раскомментировать!
     */
    if (/* last < n && */ arr[i][last] == key) {
        /* Искомый элемент найден. last - искомый индекс */
        //return FOUND(last);
        *inum=++j;
         cout <<"j-> "<< mid;
         cout <<"i-> "<<i;
          goto stop;
          
    } else {
        /* Искомый элемент не найден. Но если вам вдруг надо его
         * вставить со сдвигом, то его место - last.
         */
       // return NOTFOUND(last);
            cout<<"Nenasel";
     goto stop;
    }
 
    stop:;
}
//stop:;
//return 0;
}
1
1 / 1 / 1
Регистрация: 09.10.2014
Сообщений: 79
13.04.2015, 21:54  [ТС] 7
Спасибо, что отозвались на просьбу помощи в любом случае!
Позже посмотрю код детальнее, но идею сейчас уловил, и она как раз таки подходит для моей цели, спасибо еще раз
0
467 / 370 / 176
Регистрация: 08.04.2013
Сообщений: 1,596
14.04.2015, 07:40 8
Лучший ответ Сообщение было отмечено Bad_Trip как решение

Решение

законченный вариант
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
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
#include <iostream>
#include <string>
#include <ctime>
#include <windows.h>
 
using namespace std;
char *Rus(char *str)
{
    static char s[1024];
    CharToOem(str, s);
    return s;
}
bool f;
void output_matrix(int ** matrix, int rows, int columns)
{
    for (int i = 0; i < rows; ++i)     {
        for (int j = 0; j < columns; ++j)    {
            cout << matrix[i][j] << ' ';
        }
        cout << endl;
    }
}
 
//Копирование одной матрицы в другую.
//Первый параметр - матрица назначения, второй - матрица-источник
void copy_matrix(int ** dest_matrix, int ** source_matrix, int rows, int columns)
{
    for (int i = 0; i < rows; ++i)
    for (int j = 0; j < columns; ++j)
        dest_matrix[i][j] = source_matrix[i][j];
}
 
void LineSearch(int **arr, int rows, int cols, int key)
{
    for (int i = 0; i < rows; i++)     {
        for (int j = 0; j < cols; ++j)
        if (arr[i][j] == key)
        {
            cout << Rus( "Найденный элемент находится на ") << i + 1 ;
            cout << Rus(" строке, в ") << j + 1;
            cout << Rus(" столбце.") << endl;
            f = true;
        }
    }
}
 
void insertSort(int * arr, int arr_size)
{
    int tmp;
    for (int i = 1, j; i < arr_size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = arr[i]; //Запоминаем проверяемый элемент (тот, для которого будем искать новую позицию)
        for (j = i - 1; j >= 0; j -= 1) // цикл поиска позиции вставки в готовой последовательности
        {
            //Цикл идет в обратном направлении (от i к 0)
            //в цикле сдвигаем элементы "направо", пока не найдем позицию вставки
            if (arr[j] > tmp) //Если данный элемент меньше проверяемого, то
            {
                arr[j + 1] = arr[j]; //Сдвигаем данный элемент вправо
                //  ++swap_count;
            }
            else    break;
            
        }//++swap_count;
        //Когда цикл завершен - позиция найдена
        if ((j + 1) != i)  arr[j + 1] = tmp; // вставить проверяемый элемент в найденную позицию
       
    }
}
 
int BinarSearch(int **arr, int rows, int cols, int key, int* inum)
{
int j=0;
int first,last,mid,temp;
 
  for (int i=0; i<rows; i++) {
        /* Номер первого элемента в массиве */
    first = 0;
    /* Номер элемента в массиве, СЛЕДУЮЩЕГО ЗА последним */
    last = cols;
    /* Если просматриваемый участок непустой, first < last */
    while (first < last) {
        /* ВНИМАНИЕ! В отличие от более простого (first + last) / 2,
         * этот код устойчив к переполнениям.
         *
         * Если first и last знаковые, возможен код:
         * ((unsigned)first + (unsigned)last) >> 1.
         * Соотвественно в Java: (first + last) >>> 1.
         */
         mid = first + (last - first) / 2;
 
        if (key <= arr[i][mid])
            last = mid;
        else
            first = mid + 1;
    }
 
    /* Если условный оператор if (n == 0) и т.д. в начале опущен -
     * значит, тут раскомментировать!
     */
    if (/* last < n && */ arr[i][last] == key) {
        /* Искомый элемент найден. last - искомый индекс */
        //return FOUND(last);
         *inum=++j; 
    /*   cout <<"j-> "<< mid;    cout <<"i-> "<<i;*/
         // пробуем искать еще совпадения в строке
        temp=last;
            while (arr[i][--last]==key && last>0) *inum=++j;
            while (arr[i][++temp]==key && temp<cols) *inum=++j;
          goto stop;
          
    } else {
        /* Искомый элемент не найден. Но если вам вдруг надо его
         * вставить со сдвигом, то его место - last.
         */
       // return NOTFOUND(last); cout<<"Nenashel ";
     goto stop;
    }
 
    stop:;
}
if (j!=0)  return 0;
 else return -1;
}
 
int main()
{
    srand(time(NULL));
    setlocale(LC_ALL, "");
    string insert_rows, insert_columns, insert_key;
    int key, rows, columns, number=0, count = 0;
    int i = 0;
    int* inum=&number;
     
    cout << Rus("Введите кол-во строк матрицы: ");
    getline(cin, insert_rows);
    while (!insert_rows[0])
    {
        cout << Rus("Вы ввели Enter" )<< endl;
        getline(cin, insert_rows);
    }
    rows = atoi(insert_rows.c_str());
 
    cout << Rus("Введите кол-во стобцов матрицы: ");
    getline(cin, insert_columns);
    while (!insert_columns[0])
    {
        cout << Rus("Вы ввели Enter") << endl;
        getline(cin, insert_columns);
    }
   // columns = stoi(insert_columns);
   columns = atoi(insert_columns.c_str());
 
    int ** matrix = new int*[rows];
    int ** sorted_matrix = new int*[rows];
    //Динамическое создание двумерного массива
    for (int count = 0; count < rows; count++)
    {
        matrix[count] = new int[columns];
        sorted_matrix[count] = new int[columns];
    }
 
    //Заполнение и вывод массива 
    for (int i = 0; i < rows; ++i) //Проходим по всем строкам
    {
        matrix[i] = new int[columns];//Выделяем память под элементы строки
        sorted_matrix[i] = new int[columns];//Выделяем память под элементы строки
        for (int j = 0; j < columns; ++j) //проходим по элементам строки
        {
            matrix[i][j] = rand() % 10; //Генерируем число в интервале [10,99]
        }
    }
    cout << Rus("Исходная матрица:\n");
    output_matrix(matrix, rows, columns);
    cout << Rus( "Искомый элемент: ");
    getline(cin, insert_key);
    while (!insert_key[0])
    {
        cout << "Вы ввели Enter" << endl;
        getline(cin, insert_key);
    }
   // key = stoi(insert_key);
      key = atoi(insert_key.c_str());
    LineSearch(&matrix[i], rows, columns, key);
    if (!f)  cout << Rus("Элемент не найден") << endl;
 
    //////////////////////////////////////////////
    //////СОРТИРОВКА ДЛЯ БИНАРНОГО ПОИСКА/////////
    //////////////////////////////////////////////
 
    copy_matrix(sorted_matrix, matrix, rows, columns);
 
    for (int i = 0; i < rows; ++i)
    {
        insertSort(sorted_matrix[i], columns);
    }
    output_matrix(sorted_matrix, rows, columns);
  /*  cout << Rus("Искомый элемент: ");
   // cin >> key;*/
  if  ( BinarSearch(sorted_matrix, rows, columns, key, &number) !=-1) 
    {
        cout << Rus("Искомый элемент есть в массиве") << endl;
        cout << Rus("Количество совпадений = ") << number << endl;
    }
   else    cout << Rus("Искомый элемент не найден") << endl;
 
    //Удаление двумерного динамического массива
    for (int count = 0; count < rows; count++)
    {
        delete[] matrix[count];
        delete[] sorted_matrix[count];
        
    }
    delete[] matrix;
    delete[] sorted_matrix;
    return 0;
}
2
0 / 0 / 0
Регистрация: 17.05.2020
Сообщений: 1
17.05.2020, 22:17 9
#include <iostream>
using namespace std;

int main()
{

setlocale(LC_ALL, "ru");

//Сравниваем последний элемент подмассива с ключом. Если ключ меньше , то применяем алгоритм бинарного поиска и ищем в подмассиве как в обычном массиве.
const int ROW = 2;
const int COL = 4;
int arr1[ROW][COL]{ {0,4,5,43},{44,49,55,56} };
int last=0;
int key = 43;
int l = 0;
int r = COL;
bool flag = false;
int mid;
for (int i = 0; i < ROW; i++)
{


for (int j = (COL-1); j < COL; j++)
{
last=arr1[i][j];
if (key <= last)
{
while ((l <= r) && (flag != true))
{
mid = (l + r) / 2;
if (arr1[i][mid] == key)
{
flag = true;
}
if (arr1[i][mid] < key)
{
l = mid + 1;
}
else
{
r = mid - 1;
}

}

cout << arr1[i][mid] << endl;
return 0;


}

}
}



return 0;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.05.2020, 22:17
Помогаю со студенческими работами здесь

Поиск минимального числа в двумерном массиве
Программка ищет минимальное число в массиве и выводит это число и его индексы проблема в том что...

Бинарный поиск в массиве
Помогите нужна программа по поиску числа в массиве (бинарным методом). Очень очень нужно:(

Бинарный поиск в массиве с++
Помогите, пожалуйста с задачей: Создать массив из 20-ти елементов, инициализировать массив. 1)...

Бинарный поиск в массиве
Нужно написать программу для курсовой по теме : Разработка Windows приложения для бинарного поиска...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru