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

Бинарный поиск в массиве

30.04.2020, 15:48. Показов 281. Ответов 7
Метки c++ (Все метки)

Здравствуйте!
Подскажите пожалуйста, как написать программу бинарного поиска в массиве?
Вот написал пока так, но работает некорректно, не понимаю как исправить.
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
#include <conio.h>
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
int main(int argc, int key, char* argv[])
{
 
    int i, n;
    const int N = 1;
    int a[N];
 
    cout << ' ' << "Enter the demension of the array";
    cout << "\n ";
    cin >> n;
    cout << ' ' << "Input array";
    cout << "\n";
 
    for (i = 0; i < n; i++)
    {
        cout << " a[" << i << "]->" << ' ';
        cin >> a[i];
    }
 
    cout << ' ' << "Start array";
    cout << "\n ";
    for (i = 0; i < n; i++)
        cout << a[i] << ' ' << ' ' << ' ';
    cout << "\n ";
 
    cout << "Input x => ";
 
    cin >> key; // считываем ключ
 
    bool flag = false;
    int l = 0; // левая граница
    int r = 9; // правая граница
    int mid;
 
    while ((l <= r) && (flag != true)) {
        mid = (l + r) / 2;
 
        if (a[mid] == key) flag = true;
        if (a[mid] > key) r = mid - 1;
        else l = mid + 1;
    }
 
    if (flag) cout << ' ' << "a[" << mid << "] = " << key;
    else cout << ' ' << "Not found";
 
    _getch();
    return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.04.2020, 15:48
Ответы с готовыми решениями:

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

Бинарный поиск в массиве
Помогите нужна программа по поиску числа в массиве (бинарным методом). Очень очень нужно:(

Бинарный поиск в массиве
Нужно написать программу для курсовой по теме : Разработка Windows приложения для бинарного поиска...

Бинарный поиск в массиве с++
Помогите, пожалуйста с задачей: Создать массив из 20-ти елементов, инициализировать массив. 1)...

7
2017 / 1616 / 489
Регистрация: 31.05.2009
Сообщений: 3,005
30.04.2020, 16:41 2
Цитата Сообщение от mantowolf Посмотреть сообщение
const int N = 1;
int a[N];
...
cin >> n;
...
int r = 9; // правая граница
Хм...

Добавлено через 44 секунды
Цитата Сообщение от mantowolf Посмотреть сообщение
int main(int argc, int key, char* argv[])
Не бывает такого в C++
0
0 / 0 / 0
Регистрация: 02.05.2019
Сообщений: 54
30.04.2020, 17:49  [ТС] 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
#include <conio.h>
#include <cstdlib>
#include <iostream>
 
using namespace std;
 
int main(int argc, char* argv[])
{
 
    int i, n, x;
    
 
    cout << ' ' << "Enter the demension of the array";
    cout << "\n ";
    cin >> n;
    cout << ' ' << "Input array";
    cout << "\n";
    const int N = 1;
    int a[N];
 
    for (i = 0; i < n; i++)
    {
        cout << ' ' << "a[" << i << "] ->" << ' ';
        cin >> a[i];
    }
   
    cout << ' ' << "Start array";
    cout << "\n ";
    for (i = 0; i < n; i++)
        cout << a[i] << ' ';
    cout << "\n ";
 
    cout << "Input x =>" << ' ';
 
    cin >> x; // считываем ключ
 
    bool flag = false;
    int l = 0; // левая граница
    int r = n - 1; // правая граница
    int mid;
 
    while ((l <= r) && (flag != true)) {
        mid = (l + r) / 2;
 
        if (a[mid] == x) flag = true;
        if (a[mid] > x) r = mid - 1;
        else l = mid + 1;
    }
 
    if (flag) cout << ' ' << "a[" << mid << "] =" << ' ' << x << endl;
    else cout << ' ' << "Element" << ' ' << x << ' ' << "not found" << endl;
 
    _getch();
    return 0;
}
Добавлено через 1 минуту
Сейчас сделал вот так, и вроде всё работает, но...
Цитата Сообщение от mantowolf Посмотреть сообщение
int i, n, x;
cout << ' ' << "Enter the demension of the array";
cout << "\n ";
cin >> n;
cout << ' ' << "Input array";
cout << "\n";
const int N = 1;
int a[N];
Добавлено через 50 секунд
Не знаю ка сделать чтобы N был равен n

Добавлено через 2 минуты
Если я пишу что N=n, то в следующей строке int a[N]; подчёркивается N
0
2017 / 1616 / 489
Регистрация: 31.05.2009
Сообщений: 3,005
30.04.2020, 20:14 4
Цитата Сообщение от mantowolf Посмотреть сообщение
Сейчас сделал вот так, и вроде всё работает, но...
C++
1
2
3
4
5
6
7
8
9
10
const int N = 100;               // максимальная вместимость массива
int a[N];
 
int n;
cin >> n;                        // вводим число элементов с которым будем работать (0 < n <= N)
if (!cin || n < 1 || n > N) {    // ввод был прерван, либо указан недопустимый размер массива
    if (!cin.eof())              // ввод был прерван не по причине наступления ситуации "конец файла"
        cerr << "Error" << endl; // выводим сообщение в стандартный поток ошибок
    return 1;                    // завершаем работу программы
}
0
Just Do It!
3412 / 1879 / 623
Регистрация: 23.09.2014
Сообщений: 5,934
30.04.2020, 22:44 5
Цитата Сообщение от mantowolf Посмотреть сообщение
работает некорректно, не понимаю как исправить.
бинарный поиск возможен только по ОТСОРТИРОВАННОМУ массиву!

а теперь поглядим: где у вас сортировка?

Поэтому у вас семантически уб: всё будет хорошо, если повезёт со входными данными.
0
0 / 0 / 0
Регистрация: 02.05.2019
Сообщений: 54
01.05.2020, 11:15  [ТС] 6
Проверьте пожалуйста!
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
#include <conio.h>
#include <cstdlib>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(int argc, char* argv[])
{
 
    int i, n, x;
    
 
    cout << ' ' << "Enter the demension of the array";
    cout << "\n ";
    cin >> n;
    cout << ' ' << "Input array";
    cout << "\n";
    const int N = 100;
    int a[N];
 
    if (!cin || n < 1 || n > N) {
        if (!cin.eof())
            cerr << "Error" << endl;
        return 1;
    }
 
    for (i = 0; i < n; i++)
    {
        cout << ' ' << "a[" << i << "] ->" << ' ';
        cin >> a[i];
    }
    sort (a, a + n);
   
    cout << ' ' << "Start array";
    cout << "\n ";
    for (i = 0; i < n; i++)
        cout << a[i] << ' ';
    cout << "\n ";
 
 
    cout << "Input x =>" << ' ';
 
    cin >> x;
 
    bool flag = false;
    int l = 0;
    int r = n - 1;
    int mid;
 
    while ((l <= r) && (flag != true)) {
        mid = (l + r) / 2;
 
        if (a[mid] == x) flag = true;
        if (a[mid] > x) r = mid - 1;
        else l = mid + 1;
    }
 
    if (flag) cout << ' ' << "a[" << mid << "] =" << ' ' << x << endl;
    else cout << ' ' << "Element" << ' ' << x << ' ' << "not found" << endl;
 
    _getch();
    return 0;
}
Добавлено через 10 минут
Вот тут проверьте пожалуйста, немного изменил.
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
#include <conio.h>
#include <cstdlib>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int main(int argc, char* argv[])
{
 
    int i, n, x;
    
 
    cout << ' ' << "Enter the demension of the array";
    cout << "\n ";
    cin >> n;
    cout << ' ' << "Input array";
    cout << "\n";
    const int N = 100;
    int a[N];
 
    if (!cin || n < 1 || n > N) {
        if (!cin.eof())
            cerr << "Error" << endl;
        return 1;
    }
 
    for (i = 0; i < n; i++)
    {
        cout << ' ' << "a[" << i << "] ->" << ' ';
        cin >> a[i];
    }
    sort (a, a + n);
   
    cout << ' ' << "Start array";
    cout << "\n ";
    for (i = 0; i < n; i++)
        cout << a[i] << ' ';
    cout << "\n ";
 
 
    cout << "Input x =>" << ' ';
 
    cin >> x;
 
    bool flag = false;
    int l = 0;
    int r = n - 1;
    int mid;
 
    while (l < r) {
        mid = (l + r) / 2;
 
        if (a[mid] > x) r = mid;
        else l = mid + 1;
    }
 
    r--;
 
    if (a[r] == x) cout << ' ' << "a[" << r << "] =" << ' ' << x << endl;
    else cout << ' ' << "Element" << ' ' << x << ' ' << "not found" << endl;
 
    _getch();
    return 0;
}
0
Любитель чаепитий
3734 / 1793 / 562
Регистрация: 24.08.2014
Сообщений: 5,994
Записей в блоге: 1
01.05.2020, 11:16 7
Цитата Сообщение от rangerx Посмотреть сообщение
Не бывает такого в C++
вообще, вполне может быть.
это не запрещено стандартом напрямую.
в стандарте написано:
http://eel.is/c++draft/basic.start.main#2
Цитата Сообщение от §6.9.3.1
2 An implementation shall not predefine the main function. This function shall not be overloaded. Its type shall have C++ language linkage and it shall have a declared return type of type int, but otherwise its type is implementation-defined. <...>
то есть вполне может быть реализация, предоставляющая такую форму main.
на деле же такая реализация вряд ли есть.
обычно компиляторы позволяют в конец добавить ещё параметры, но не в середину.
1
0 / 0 / 0
Регистрация: 02.05.2019
Сообщений: 54
01.05.2020, 12:51  [ТС] 8
Я сделал другой:
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
#include <stdio.h>
#include <malloc.h>
#include <conio.h>
#include <iostream>
 
using namespace std;
 
int binarysearch(int a, int mass[], int n);
void InsertionSort(int n, int mass[]);
 
int main(int argc, char* argv[])
{
    int N, a;
    cout << ' ' << "Enter the demension of the array" << "\n ";
    scanf_s("%d", &N);
    int* mass;
    mass = (int*)malloc(N * sizeof(int));
    cout << ' ' << "Input array:" << "\n";
    for (int i = 0; i < N; i++) {
        cout << " a[" << i << "] -> ";
        scanf_s("%d", &mass[i]);
    }
    InsertionSort(N, mass);
    cout << ' ' << "Sorted array:" << "\n" << ' ';
    for (int i = 0; i < N; i++)
        printf("%d ", mass[i]);
    cout << "\n";
    cout << ' ' << "Input x =>" << ' ';
    scanf_s("%d", &a);
    int k;
    k = binarysearch(a, mass, N);
    if (k != -1)
        cout << ' ' << "a[" << k << "] =" << ' ' << a << endl;
    else
        cout << ' ' << "Element" << ' ' << a << ' ' << "not found!" << endl;
    free(mass);
    _getch();
    return 0;
}
 
int binarysearch(int a, int mass[], int n)
{
    int low, high, middle;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        middle = (low + high) / 2;
        if (a < mass[middle])
            high = middle - 1;
        else if (a > mass[middle])
            low = middle + 1;
        else
            return middle;
    }
    return -1;
}
 
void InsertionSort(int n, int mass[])
{
    int newElement, location;
 
    for (int i = 1; i < n; i++)
    {
        newElement = mass[i];
        location = i - 1;
        while (location >= 0 && mass[location] > newElement)
        {
            mass[location + 1] = mass[location];
            location = location - 1;
        }
        mass[location + 1] = newElement;
    }
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.05.2020, 12:51
Помогаю со студенческими работами здесь

Бинарный поиск элемента в массиве
Суть - программа ищет число по формуле K=(a+b)/2 бинарным поиском, и выводит его порядковый номер...

Бинарный поиск в одномерном массиве
Заполнить одномерный массив из n элементов по формуле соотв-ей вашему варианту задания....

Бинарный поиск в упорядоченном массиве
Задали реализовать бинарный поиск в упорядоченном массиве.Уже пол дня творю,3 листа исписал и...

Бинарный поиск числа в массиве
Здравствуйте имеется программка в которую через клаву вводишь определенное кол-во чисел(кол-во...

Бинарный поиск числа в массиве
Дан упорядоченный массив чисел от 0 до 100. Необходимо выполнить бинарный поиск числа 25. Как его...

Сортировка, линейный и бинарный поиск в массиве
1. Ввести элементы массива Х(15). 2. Ввести значение целевого элемента (А). 3. Найти А с помощью...


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

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

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