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

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

Новые блоги и статьи Все статьи Все блоги /
Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .	Использование SDL3-callbacks вместо функции main() на Android, Desktop и WebAssembly 8Observer8 24.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .

@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

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

Решение