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

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

Новые блоги и статьи Все статьи Все блоги /
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .

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

@marat_miaki 518 / 410 / 188 Регистрация: 08.04.2013 Сообщений: 1,750
	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

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

Решение