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

@Bad_Trip · Регистрация: 09.10.2014

Студворк — интернет-сервис помощи студентам

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

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

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;
}

@marat_miaki · 12.04.2015, 20:52

объяви count как глобальная переменная, то есть int count=0; до int main() для int BinarSearch или используй другую, т.к ты её еще для чего то исползуешь

@Bad_Trip · 12.04.2015, 21:17 **[ТС]**

не помогло

Добавлено через 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;
}

@marat_miaki · 12.04.2015, 21:31

Думаю для поиска и подсчета элементов в массиве не тот подход. Бинарный - способ быстро найти первый искомый элемент в отсортированном массиве, достаточно большом. А дальше искать и считать другим способом

@Bad_Trip · 12.04.2015, 21:54 **[ТС]**

Может этот вариант будет ближе?

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;
}

@marat_miaki · 13.04.2015, 18:21

Вот поработал, но срабатывает бинарный поиск почему то не всегда. Иногда пропускает, иногда срабатывает правильно. Подсчет по строке когда больше одного совпадения пока не реализован.

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;
}

@Bad_Trip · 13.04.2015, 21:54 **[ТС]**

Спасибо, что отозвались на просьбу помощи в любом случае!
Позже посмотрю код детальнее, но идею сейчас уловил, и она как раз таки подходит для моей цели, спасибо еще раз

@marat_miaki · 14.04.2015, 07:40

законченный вариант

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;
}

@Avicenna · 17.05.2020, 22:17

#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;
}

Новые блоги и статьи Все статьи Все блоги /
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025	Расскажи мне о Мире, бродяга kumehtar 12.11.2025 — Расскажи мне о Мире, бродяга, Ты же видел моря и метели. Как сменялись короны и стяги, Как эпохи стрелою летели. - Этот мир — это крылья и горы, Снег и пламя, любовь и тревоги, И бескрайние. . .

@marat_miaki 518 / 410 / 188 Регистрация: 08.04.2013 Сообщений: 1,749
	12.04.2015, 20:52
	объяви count как глобальная переменная, то есть int count=0; до int main() для int BinarSearch или используй другую, т.к ты её еще для чего то исползуешь 0

@marat_miaki 518 / 410 / 188 Регистрация: 08.04.2013 Сообщений: 1,749
	12.04.2015, 21:31
	Думаю для поиска и подсчета элементов в массиве не тот подход. Бинарный - способ быстро найти первый искомый элемент в отсортированном массиве, достаточно большом. А дальше искать и считать другим способом 0

@Bad_Trip 1 / 1 / 1 Регистрация: 09.10.2014 Сообщений: 79
	13.04.2015, 21:54 [ТС]
	Спасибо, что отозвались на просьбу помощи в любом случае! Позже посмотрю код детальнее, но идею сейчас уловил, и она как раз таки подходит для моей цели, спасибо еще раз 0

@Avicenna 0 / 0 / 0 Регистрация: 17.05.2020 Сообщений: 1
	17.05.2020, 22:17
	#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

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

Решение