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

Определение границ вхождения одинаковых элементов в упорядоченный массив при использовании бин. поиска

15.10.2018, 18:21. Показов 280. Ответов 0
Метки нет (Все метки)

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
#include <iostream>
#include <map>
 
using namespace std;
 
map <int, int[2]> mp;
 
int binarySearchLeft(int target,int left, int right, int arr[]);
int binarySearchRight(int target, int left, int right, int arr[]);
 
int main() {
    freopen("binsearch.in", "r", stdin);
    freopen("binsearch.out", "w", stdout);
    int n, m;
    cin >> n;
    int *arr = new int[n];
    for(int i = 0; i < n; ++i){
        cin >> arr[i];
    }
    cin >> m;
    int *a = new int[m];
    //map <int, int[2]>::iterator it= mp.begin();
    for (int j = 0; j < m; ++j) {
        int i;
        cin >> i;
        mp[i][0] = 0;
        mp[i][1] = 0;
        a[j]=i;
    }
    for (int j = 0; j < m; ++j) {
        int left=0; int right = n-1;
        int index = a[j];
        if (a[j] == a[j+1]) continue;
        int p1 = binarySearchLeft(index, left, right-1, arr);
        cout << p1;
        cout << " ";
        int p2 = binarySearchRight(index, left, right, arr);
        if (p1 != -1){
            cout << p2;
        } else{
            cout << -1;
        }
        cout << endl;
    }
    return 0;
}
 
int binarySearchLeft(int target,int left, int right, int arr[]){
    bool ident = true;
    while (left <= right){
        int mid = (left + right)/2;
        if (target == arr[mid]) {
            return mid + 1;
            ident = false;
        }
        if (target > arr[mid])
            left = mid + 1;
        else
            right = mid - 1;
    }
    if (ident) return -1;
}
 
int binarySearchRight(int target, int left, int right, int arr[]) {
    int mid=(left+right)/2;
    if (left>right)
        return left;
    if (arr[mid]>target)
        return binarySearchRight (target,left,mid-1,arr);
    else
        return binarySearchRight (target,mid+1,right,arr);
}
Вот,собственно, код Отчего-то неправильно работает на массивах из одинаковых элементов.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.10.2018, 18:21
Ответы с готовыми решениями:

Сформировать упорядоченный массив из 20 элементов. Методом бинарного поиска определить, содержит ли он заданное число
нужна полная программа. Сформировать массив а, упорядоченный по возрастанию. Методом бинарного...

Методом бинарного поиска определить, содержит ли упорядоченный массив заданное число
Сформировать массив а, упорядоченный по возрастанию. Методом бинарного поиска определить, содержит...

Вывести на печать массив X, массив Z, массив Y, произведение элементов массива X, упорядоченный массив Y
Вывести на печать массив X, массив Z, массив Y, произведение элементов массива X, упорядоченный...

Нужен совет по реализации бин. поиска
Всем привет! Нужно сделать быстрый поиск по контейнеру! Реализованы операции добавления, удаления...

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

Рекурсив. обход бин. дерева поиска
Доброе утро. Имею следующий код : print_tree(bintree *p){ if(p){ print_tree(p-&gt;left);...

Оставить в списке только первые вхождения одинаковых элементов
помогите, пожалуйста, решить задачу на F#: Оставить в списке только первые вхождения одинаковых...

Оставить в списке только первые вхождения одинаковых элементов
В составе программы описать функцию, которая оставляет в списке только первые вхождения одинаковых...

Оставить в списке только первые вхождения одинаковых элементов
Дан список L, элементы которого являются действительными числами. Оставить в списке только первые...

Оставить в созданном списке только первые вхождения одинаковых элементов
Помогите, пожалуйста, разобраться с задачкой, при компиляции выдает ошибки в 10, 15, 32 37 строках,...

Массив: Сформируйте массив C[n+m], состоящий из элементов массивов А и В, упорядоченный по возрастанию.
написать программы! Вот задания! Я болел и просто не успею все зделать! 1)Дан массив целых чисел....


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

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

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