2 / 1 / 1
Регистрация: 01.05.2020
Сообщений: 19
1

Бинарный поиск парных елементов в массиве B, которые есть в массиве А

19.03.2021, 13:58. Показов 1259. Ответов 3

Не работает цикл, пробовал разные условия, однако оно либо выводит много раз одно и тоже, либо выводит один раз и прекращает цикл.

Задание:
Парные елементы масива А, которые есть в масиве В. Алгоритмы поиска: Линейный, бинарный.
Также нужно сделать счетчик операций.



С линейным проблем нет, бинарный в итоге не работает, по сути нужно делать его как отдельную функцию, однако оно не работало так, также расмеры массивов должны быть 500 елементов, однако я сделал для проверки 10.
числа в массива должны быть рандомными от 0 до Н-1
Н=1000


Буду благодарен за обьяснение моих ошибок и указание верніх путей.

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
#include <iostream>
#include <ctime>
#include <random>
#include <clocale>
int qsort(int m[], const int size);
static int S = 0;
using namespace std;
 
int main()
{
    setlocale(0, "");
    srand(time(NULL));
    const int N = 1000, _size = 20;
    int A[_size], B[_size], LB = 0, UB = _size;
    bool q = false;
    for (int i = 0; i < _size; i++)
    {
        A[i] = 1 + rand() % 10;
        B[i] = 1 + rand() % 10;
    }
    for (int i = 0; i < _size; i++)
    {
        cout << A[i] << "  ";
    }
    cout << endl;
    for (int i = 0; i < _size; i++)
    {
        cout << B[i] << "  ";
    }
    qsort(A, _size);
    qsort(B, _size);
    cout << endl;
    for (int i = 0; i < _size; i++)
    {
        cout << A[i] << "  ";
    }
    cout << endl;
    for (int i = 0; i < _size; i++)
    {
        cout << B[i] << "  ";
    }
    cout << endl << "Елементи масиву А якi зустрычаються в масивi B" << endl;
    for (int i = 0; i < _size; i++)
    {
        int M, Key = B[i];
        do
        {
            M = LB + (UB - LB) / 2; // шукаємо середину відрізку
            if (Key < A[M])
            {
                UB = --M; // переходимо у ліву частину
            }
            else
            {
                if (Key > A[M])
                {
                    LB = ++M; // переходимо у праву частину
                }
                else
                {
                    //if (A[M] % 2 == 0)
                    //{
                        cout << A[M] << "  ";
                        q = false;
                    //}
                }
            }
            if (LB > UB)
            {
                return -1; // не знайдено
            }
        } while (q);
 
        //cout << endl << S;
    }
}
int qsort(int m[], const int size)
{
    int temp;
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (m[j] > m[j + 1]) {
                temp = m[j];
                m[j] = m[j + 1];
                m[j + 1] = temp;
            }
        }
    }
 
    return 1;
}
Вот вариант кода с алгоритмом в виде отдельной функции

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
#include <iostream>
#include <ctime>
#include <random>
#include <clocale>
int qsort(int m[], const int size);
static int BinarySearch(int a[], int b[], int Lb, int Ub, int k);
int S = 0;
using namespace std;
 
int main()
{
    setlocale(0, "");
    srand(time(NULL));
    const int N = 1000, _size = 10;
    int A[_size], B[_size], LB = 0, UB = 10;
    bool q = false;
    for (int i = 0; i < _size; i++)
    {
        A[i] = rand() % 6;
        B[i] = rand() % 6;
    }
    /*for (int i = 0; i < 10; i++)
    {
        cout << A[i] << "  ";
    }
    cout << endl;
    for (int i = 0; i < 10; i++)
    {
        cout << B[i] << "  ";
    }*/
    qsort(A, _size);
    qsort(B, _size);
    cout << "Елементи масиву А якi зустрычаються в масивi B" << endl;
    for (int m = 0; m < _size; m++)
    {
        cout <<BinarySearch(A, B, LB, UB, m) << "  ";
    }
    cout << endl << "Кiлькiсть операцiй витрачених на алгоритм бiнарного пошуку"<<S;
}
 
int qsort(int m[], const int size)
{
    int temp;
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (m[j] > m[j + 1]) {
                temp = m[j];
                m[j] = m[j + 1];
                m[j + 1] = temp;
            }
        }
    }
 
    return 1;
}
 
static int BinarySearch(int a[], int b[], int Left, int Right, int k)
{
    int M, key = b[k];
    do
    {
        S++;
        M = Left + (Right - Left) / 2;
        if (a[M] < b[k])
        {
            Left = ++M;
        }
        else
        {
            if (a[M] > b[k])
            {
                    Right = M--;
            }
            else
            {
                if (a[M] % 2 == 0)
                return a[M];
            }
        }
        if (Left > Right)
        {
            return -1;
        }
    } while (true);
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.03.2021, 13:58
Ответы с готовыми решениями:

В одномерном массиве состоящем из n вещественных элементов сделать бинарный поиск числа А в упорядоченном массиве
Всем привет помогите решить задачи 1) В одномерном массиве состоящем из n вещественных элементов:...

Бинарный поиск: Если в первом массиве есть такое же число, как и во втором, то написать YES
Можете помочь составить бинарный поиск вида: если в первом массиве есть такое же число, как и во...

Найти элементы, которые есть в массиве А в нескольких экземплярах и отсутствуют в массиве В
Здравствуйте! Прошу помощи с заданием. Задание звучит так : найти элементы, которые есть в...

Вывести элементы, которые есть в массиве А в нескольких экземплярах и отсутствуют в массиве В
Задание : вывести на экран элементы, которые есть в массиве А в нескольких экземплярах и...

3
2 / 1 / 1
Регистрация: 01.05.2020
Сообщений: 19
20.03.2021, 13:52  [ТС] 2
Смог решить часть проблем, однако когда массив большой оно не выводит нужные элементы после определенного количества

Код с поиском в отдельной функции:
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
#include <iostream>
#include <ctime>
#include <random>
#include <clocale>
int Binary_Search(int A[], int B[], const int size, bool q, int LB, int UB, int key);
int qsort(int m[], const int size);
static int S = 0;
using namespace std;
 
int main()
{
    setlocale(0, "");
    srand(time(NULL));
    const int N = 1000, _size = 40;
    int A[_size], B[_size], LB = 0, UB = _size, i = 0;
    bool q = true;
    for (int i = 0; i < _size; i++)
    {
        A[i] = 1 + rand() % 20;
        B[i] = 1 + rand() % 20;
    }
    /*for (i = 0; i < _size; i++)
    {
        cout << A[i] << "  ";
    }
    cout << endl;
    for (i = 0; i < _size; i++)
    {
        cout << B[i] << "  ";
    }*/
    qsort(A, _size);
    qsort(B, _size);
    cout << endl;
    for (i = 0; i < _size; i++)
    {
        cout << A[i] << "  ";
    }
    cout << endl;
    for (i = 0; i < _size; i++)
    {
        cout << B[i] << "  ";
    }
    cout << endl << "Елементи масиву А якi зустрiчаються в масивi B" << endl;
    for (int i = 0; i < _size; i++)
    {
        int key = B[i];
        cout << Binary_Search(A, B, _size, q, LB, UB, key) << "   ";
    }
    cout << endl << S;
}
int Binary_Search(int A[], int B[], const int size, bool q, int LB, int UB, int key)
{
    q = true;
    int M = 0;
    LB = 0;
    UB = size;
    if (key % 2 == 0)
    {
        do
        {
            S++;
            M = LB + (UB - LB) / 2;
            if (key < A[M])
            {
                UB = --M;
            }
            else
            {
                if (key > A[M])
                {
                    LB = ++M;
                }
                else
                {
                    return A[M];
                    q = false;
                }
            }
        } while (q);
    //cout << endl << S;
    }
}
 
 
 
int qsort(int m[], const int size)
{
    int temp;
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - i - 1; j++) {
            if (m[j] > m[j + 1]) {
                temp = m[j];
                m[j] = m[j + 1];
                m[j + 1] = temp;
            }
        }
    }
 
    return 1;
}

Код с поиском в int main

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
#include <iostream>
#include <ctime>
#include <random>
#include <clocale>
int qsort(int m[], const int size);
static int S = 0;
using namespace std;
 
int main()
{
    setlocale(0, "");
    srand(time(NULL));
    const int N = 1000, _size = 500;
    int A[_size], B[_size], LB = 0, UB = _size, i = 0;
    bool q = true;
    for (int i = 0; i < _size; i++)
    {
        A[i] = rand() % (N - 1);
        B[i] = rand() % (N - 1);
    }
    /*for (i = 0; i < _size; i++)
    {
        cout << A[i] << "  ";
    }
    cout << endl;
    for (i = 0; i < _size; i++)
    {
        cout << B[i] << "  ";
    }*/
    qsort(A, _size);
    qsort(B, _size);
    cout << endl;
    for (i = 0; i < _size; i++)
    {
        cout << A[i] << "  ";
    }
    cout << endl;
    for (i = 0; i < _size; i++)
    {
        cout << B[i] << "  ";
    }
    cout << endl << "Елементи масиву А якi зустрiчаються в масивi B" << endl;
    for (i = 0; i < _size; i++)
    {
        q = true;
        int M, Key = B[i];
        LB = 0;
        UB = _size;
        if (Key % 2 == 0)
        {
            do
            {
                S++;
                M = LB + (UB - LB) / 2;
                if (Key < A[M])
                {
                    UB = --M;
                }
                else
                {
                    if (Key > A[M])
                    {
                        LB = ++M;
                    }
                    else
                    {
                        cout << A[M] << "  ";
                        q = false;
                    }
                }
            } while (q);
            //cout << endl << S;
        }
    }
    cout << endl << S;
}
    int qsort(int m[], const int size)
    {
        int temp;
        for (int i = 0; i < size - 1; i++) {
            for (int j = 0; j < size - i - 1; j++) {
                if (m[j] > m[j + 1]) {
                    temp = m[j];
                    m[j] = m[j + 1];
                    m[j + 1] = temp;
                }
            }
        }
 
        return 1;
    }
0
1642 / 1091 / 487
Регистрация: 17.07.2012
Сообщений: 5,345
20.03.2021, 15:06 3
Лучший ответ Сообщение было отмечено MurkyWater как решение

Решение

Цитата Сообщение от MurkyWater Посмотреть сообщение
LB = 0, UB = _size
Эти переменные должны быть внутри функции бинарного поиска, не нужно их создавать в main и передавать в бинарный поиск. У вас по всему коду раскидано кучу переменных, переменная S глобальная зачем-то, хотя можно в main завести переменную и назвать её как-то типа count / even_count и определить её прямо перед циклом(т.е поближе к той части кода, где эта переменная будет использоваться) в котором находятся нужные элементы. Названия переменных / функций в разном стиле(мелочь, но мне кажется стоит соблюдать какой-то единый code style) = там с маленькой буквы, там с большой. Бинарный поиск должен принимать указатель на массив, размер массива и число, и возвращать true / false, не нужно сразу писать функцию которая полностью решает задачу, гораздо проще разбить задачу на подзадачи. У вас бинарный поиск возвращает число если оно нашлось, а если не нашлось что возвращает ? Никак не определишь нашлось ли число или нет - в int нет специального значения которое говорит о том что это не число. Сам бинарный поиск можно писать по-разному, но мне больше всего нравится с инвариантом.
Пусть нужно найти key, и у нас есть lower(нижняя граница), upper(верхняя граница) и мы считаем что a[lower] <= key < a[upper]. upper = size, элемента с этим индексом нет, можно считать что a[upper] бесконечно большое число которое больше чем key. lower = 0. И если в цикле поддерживать инвариант код становится проще. Нашли mid(середину). Если key < a[mid] значит mid новая верхняя граница(поддерживаем инвариант, у нас всегда key должен быть строго меньше чем a[upper]). Если key >= a[mid] значит новая нижняя граница(и опять же не надо никаких +-1). Цикл завершим когда upper - lower <= 1, и тогда вспоминая инвариант a[lower] <= key < a[upper], понимаем что либо нужный элемент в lower либо его просто нет.
Я код особо не тестил, но вроде все правильно.
Код
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
#include <iostream>
#include <ctime>
#include <random>
#include <clocale>
 
using namespace std;
 
bool binary_search(int a[], const int size, int key);
void sort(int a[], const int size);
 
int main()
{
    setlocale(0, "");
    srand(time(NULL));
    const int N = 1000, size = 40;
    int a[size], b[size];
    
    for (int i = 0; i < size; i++)
    {
        a[i] = 1 + rand() % 20;
        b[i] = 1 + rand() % 20;
    }
    /*for (i = 0; i < size; i++)
    {
        cout << a[i] << "  ";
    }
    cout << endl;
    for (i = 0; i < size; i++)
    {
        cout << b[i] << "  ";
    }*/
    
    // один массив можно не сортировать, поиск все равно в другом массиве
    //sort(a, size);
    sort(b, size);
    cout << endl;
    for (int i = 0; i < size; i++)
    {
        cout << a[i] << "  ";
    }
    cout << endl;
    for (int i = 0; i < size; i++)
    {
        cout << b[i] << "  ";
    }
    cout << endl << "Елементи масиву А якi зустрiчаються в масивi B" << endl;
    int even_count = 0;
    for (int i = 0; i < size; i++)
    {
        if (a[i] % 2 == 0 && binary_search(b, size, a[i])) {
            cout << a[i] << "   ";
            even_count++;
        }
    }
    cout << endl << "Количество: " << even_count;
}
 
bool binary_search(int a[], const int size, int key)
{
    int lower = 0;
    int upper = size;
    
    do
    {
        int mid = lower + (upper - lower) / 2;
        if (key < a[mid])
        {
            upper = mid;
        }
        else
        {
            lower = mid;
        }
    } while (upper - lower > 1);
    return a[lower] == key;
}
 
void sort(int a[], const int size)
{
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = 0; j < size - i - 1; j++)
        {
            if (a[j] > a[j + 1])
            {
                int temp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = temp;
            }
        }
    }
}
2
2 / 1 / 1
Регистрация: 01.05.2020
Сообщений: 19
20.03.2021, 15:20  [ТС] 4
Спасибо большое за помощь и пояснение
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.03.2021, 15:20
Помогаю со студенческими работами здесь

Найти элементы, которые есть в первом массиве, и которых нет во втором массиве
Даны два одномерных массива из целых чисел. Найти элементы, которые есть в первом массиве, и...

Найти элементы, которые есть в первом массиве, и которых нет во втором массиве.
1. Даны два одномерных массива из целых чисел. Найти элементы, которые есть в первом массиве, и...

Найти элементы, которые есть в первом массиве, и которых нет во втором массиве
Даны два одномерных массива из целых чисел. Найти элементы, которые есть в первом массиве, и...

Ввести массивы А и В. В массив С скопировать те элементы, которые есть в массиве А, но которых нет в массиве В.
Помогите решить Ввести массивы А и В. В массив С скопировать те элементы, которые есть в...

В массив С скопировать те элементы, которые есть и в массиве А и в массиве В
Ввести массивы А и В. В массив С скопировать те элементы, которые есть и в массиве А ...

В массив С скопировать те элементы, которые есть и в массиве А и в массиве В
Всем добрый день!Сегодня в превый раз увидел C#! Язык C#,программа в консоле. Задание:&quot;Ввести...


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

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

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