Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 240, средняя оценка - 4.93
diana92
4 / 4 / 1
Регистрация: 25.10.2009
Сообщений: 36
#1

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

01.11.2009, 21:30. Просмотров 32294. Ответов 19
Метки нет (Все метки)

Помогите нужна программа по поиску числа в массиве (бинарным методом). Очень очень нужно
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.11.2009, 21:30     Бинарный поиск в массиве
Посмотрите здесь:

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

Бинарный поиск числа в массиве - C++
Дан упорядоченный массив чисел от 0 до 100. Необходимо выполнить бинарный поиск числа 25. Как его реализовать? Я знаю, что в теории должно...

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

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

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

Бинарный поиск в упорядоченном по возрастанию массиве - C++
Напишите программу, которая, используя метод бинарного поиска, выполняет поиск в упорядоченном по возрастанию массиве.

Двоичный (бинарный) поиск элемента в двумерном массиве - C++
Доброго времени суток. есть вот такое задание: Написать функцию, реализующую алгоритм бинарного поиска заданного ключа в двухмерном...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Monte-Cristo
2787 / 1373 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
01.11.2009, 21:41     Бинарный поиск в массиве #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
#include <iostream>
using namespace std;
 
int BinSearch(int *M, int n, int k);
 
int main()
{
    const int n=5;
    int A[n];
    int x;
    
    for (size_t i=0; i<n; i++)
    {
        cout << "Please, input A[" << i+1 << "] = ";
        cin >> A[i];
    }
    
    cout << "find this -> ";
    cin >> x;
    
    cout << BinSearch(A, n, x);
    
    return 0;
}
 
int BinSearch(int *M, int n, int k)
{
    int L = 0;
    int R = n;
 
    int m;
    int z = 0;
 
    while (L<R)
    {
        z++;
        m = (L+R)/2;
        if (k > M[m]) L = m;
        if (k < M[m]) R = m;
        if (k == M[m]) break;
    }
 
    return m;
}
diana92
4 / 4 / 1
Регистрация: 25.10.2009
Сообщений: 36
01.11.2009, 21:46  [ТС]     Бинарный поиск в массиве #3
да типа только не надо вводить числа в массив, они будут введенны уже
Можно так?
audiophile
9 / 9 / 0
Регистрация: 01.11.2009
Сообщений: 67
01.11.2009, 21:46     Бинарный поиск в массиве #4
Или так:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class T> int BinSearch( T A[],  T key,  int low, int high)
{
         if ( low > high )
         {
              cout << "ERROR!";
              return -1;
         };
         int mid = ( low + high ) / 2;
         if ( A[mid] == key )
            return mid;
         if ( A[mid] < key)
            BinSearch(A,key,mid+1,high);
         if ( A[mid] > key )
            BinSearch(A,key,low,mid-1);
}
CyBOSSeR
Эксперт C++
2299 / 1669 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.11.2009, 21:46     Бинарный поиск в массиве #5
Monte-Cristo, а что возвратит приведенная тобой функция BinSearch в случае, если искомый элемент отсутствует?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Поиск ключа в упорядоченном массиве
// Массив должен быть упорядочен по возрастанию (неубыванию)
// Функция возвращает индекс искомого элемента
// В случае отсутствия искомого элемента возвращает -1.
int BinSearch(const int* arr, int count, int key) 
{
  int l = 0;            // нижняя граница
  int u = count - 1;    // верхняя граница
 
  while (l <= u) {
    int m = (l + u) / 2;
    if (arr[m] == key) return m;
    if (arr[m] < key) l = m + 1;
    if (arr[m] > key) u = m - 1;
  }
  return -1;
}
audiophile
9 / 9 / 0
Регистрация: 01.11.2009
Сообщений: 67
01.11.2009, 21:47     Бинарный поиск в массиве #6
diana92, бинарный поиск предполагает, что числа в массиве, где он будет производиться, уже отсортированы по возрастанию!
Gravity
562 / 556 / 39
Регистрация: 29.01.2009
Сообщений: 1,274
01.11.2009, 21:48     Бинарный поиск в массиве #7
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
#include <stdio.h>
 
int binsearch(int x, int v[], int n)
{
    int low, high, mid;
 
    low = 0;
    high = n;
    while(low <= high) {
        mid = (low + high) / 2; 
        if(x < v[mid])              
            high = mid - 1;
        else if(x > v[mid])
            low = mid + 1;
        else
            return mid;
    }
    return -1;
}
 
int main()
{
    int i, ret, num, nsize = 6, a[6];
    
    /* заполнение массива */
    for(i = 0; i < nsize; i++) {
        a[i] = i;
        printf("%d ", a[i]);
    }
    
    num = 1;
 
    /* поиск числа num в массиве a */
    if( (ret = binsearch(num, a, nsize)) < 0)
        printf("\nЧисло %d отсутствует в массиве\n", num);
    else
        printf("\nЧисло %d находится в a[%d]\n", num, ret);
    return 0;
}
diana92
4 / 4 / 1
Регистрация: 25.10.2009
Сообщений: 36
01.11.2009, 22:06  [ТС]     Бинарный поиск в массиве #8
Цитата Сообщение от Monte-Cristo Посмотреть сообщение
Например так
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
#include <iostream>
using namespace std;
 
int BinSearch(int *M, int n, int k);
 
int main()
{
    const int n=5;
    int A[n];
    int x;
    
    for (size_t i=0; i<n; i++)
    {
        cout << "Please, input A[" << i+1 << "] = ";
        cin >> A[i];
    }
    
    cout << "find this -> ";
    cin >> x;
    
    cout << BinSearch(A, n, x);
    
    return 0;
}
 
int BinSearch(int *M, int n, int k)
{
    int L = 0;
    int R = n;
 
    int m;
    int z = 0;
 
    while (L<R)
    {
        z++;
        m = (L+R)/2;
        if (k > M[m]) L = m;
        if (k < M[m]) R = m;
        if (k == M[m]) break;
    }
 
    return m;
}
я поменяла так

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
#include <iostream>
using namespace std;
 
 
 
int main()
{
    int Binsearch;
    const int n=5;
    int A[n]={1,2,3,4,5};
    int x;
    
   
    
    cout << "find this -> ";
    cin >> x;
    
    cout << BinSearch(A, n, x);
    
    return 0;
}
 
int BinSearch(int *M, int n, int k)
{
    int L = 0;
    int R = n;
 
    int m;
    int z = 0;
 
    while (L<R)
    {
        z++;
        m = (L+R)/2;
        if (k > M[m]) L = m;
        if (k < M[m]) R = m;
        if (k == M[m]) break;
    }
 
    return 0;
}
просто надо так чтобы числа уже были введенные, массив должен задаваться в int main,а не после и заканчивалось бы return 0, и если это число есть показало бы "yes"

подскажите в чем ошибка?
audiophile
9 / 9 / 0
Регистрация: 01.11.2009
Сообщений: 67
01.11.2009, 22:12     Бинарный поиск в массиве #9
diana92, почему вы 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
#include <iostream>
using namespace std;
 
int BinSearch(int *M, int n, int k)
{
    int L = 0;
    int R = n;
    
    int m;
    int z = 0;
    
    while (L<R)
    {
        z++;
        m = (L+R)/2;
        if (k > M[m]) L = m;
        if (k < M[m]) R = m;
        if (k == M[m]) break;
    }
    
    return m;
} 
 
int main()
{
    const int n=5;
    int A[n]={1,2,3,4,5};
    int x;
    
    cout << "find this -> ";
    cin >> x;
    
    cout << BinSearch(A, n, x);
    
    return 0;
}
CyBOSSeR
Эксперт C++
2299 / 1669 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.11.2009, 22:13     Бинарный поиск в массиве #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
#include <iostream>
 
using namespace std;
 
int BinSearch(const int* arr, int count, int key);
 
int main()
{
    const int n = 5;
    int arr[n] = {1, 2, 3, 4, 5};
    int key;
    
    cout << "key: ";
    cin >> key;
 
    if(BinSearch(arr, n, key) != -1)
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
    
    return 0;
}
 
int BinSearch(const int* arr, int count, int key) 
{
  int l = 0;            // нижняя граница
  int u = count - 1;    // верхняя граница
 
  while (l <= u) {
    int m = (l + u) / 2;
    if (arr[m] == key) return m;
    if (arr[m] < key) l = m + 1;
    if (arr[m] > key) u = m - 1;
  }
  return -1;
}
diana92
4 / 4 / 1
Регистрация: 25.10.2009
Сообщений: 36
01.11.2009, 22:14  [ТС]     Бинарный поиск в массиве #11
audiophile , просто мой препод не разрешает применять то,что мы еще не проходиди, а мы только return 0 пока прошли
audiophile
9 / 9 / 0
Регистрация: 01.11.2009
Сообщений: 67
01.11.2009, 22:16     Бинарный поиск в массиве #12
Цитата Сообщение от diana92 Посмотреть сообщение
а мы только return 0 пока прошли
Ээээ... Как бы некоторая функция может возвращать любое число, объект... Вы будете проходить их все? 0,1,2,3,...? Вы не так его поняли.
diana92
4 / 4 / 1
Регистрация: 25.10.2009
Сообщений: 36
01.11.2009, 22:17  [ТС]     Бинарный поиск в массиве #13
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Так попробуй:
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
#include <iostream>
 
using namespace std;
 
int main()
{
    const int n = 5;
    int arr[n] = {1, 2, 3, 4, 5};
    int key;
    
    cout << "key: ";
    cin >> key;
 
    if(BinSearch(arr, n, key) != -1)
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
    
    return 0;
}
 
int BinSearch(const int* arr, int count, int key) 
{
  int l = 0;            // нижняя граница
  int u = count - 1;    // верхняя граница
 
  while (l <= u) {
    int m = (l + u) / 2;
    if (arr[m] == key) return m;
    if (arr[m] < key) l = m + 1;
    if (arr[m] > key) u = m - 1;
  }
  return -1;
}


2 ошибки выдает
audiophile
9 / 9 / 0
Регистрация: 01.11.2009
Сообщений: 67
01.11.2009, 22:19     Бинарный поиск в массиве #14
Цитата Сообщение от diana92 Посмотреть сообщение
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
#include <iostream>
using namespace std;
 
int BinSearch(const int*, int, int); 
 
int main()
{
    const int n = 5;
    int arr[n] = {1, 2, 3, 4, 5};
    int key;
    
    cout << "key: ";
    cin >> key;
    
    if(BinSearch(arr, n, key) != -1)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    
    return 0;
}
 
int BinSearch(const int* arr, int count, int key) 
{
    int l = 0;            // нижняя граница
    int u = count - 1;    // верхняя граница
    
    while (l <= u) {
        int m = (l + u) / 2;
        if (arr[m] == key) return m;
        if (arr[m] < key) l = m + 1;
        if (arr[m] > key) u = m - 1;
    }
    return -1;
}
Вторая, видимо — недостающий знак ";" после while. Так надо отвыкать от visual c++ .
CyBOSSeR
Эксперт C++
2299 / 1669 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.11.2009, 22:19     Бинарный поиск в массиве #15
Вот это скопируй и запусти.
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
#include <iostream>
 
using namespace std;
 
int BinSearch(const int* arr, int count, int key);
 
int main()
{
    const int n = 5;
    int arr[n] = {1, 2, 3, 4, 5};
    int key;
    
    cout << "key: ";
    cin >> key;
 
    if(BinSearch(arr, n, key) != -1)
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
    
    return 0;
}
 
int BinSearch(const int* arr, int count, int key) 
{
  int l = 0;            // нижняя граница
  int u = count - 1;    // верхняя граница
 
  while (l <= u) {
    int m = (l + u) / 2;
    if (arr[m] == key) return m;
    if (arr[m] < key) l = m + 1;
    if (arr[m] > key) u = m - 1;
  }
  return -1;
}
И сразу копируй в форум ошибки, которые возникают, чтобы было понятно что к чему.
Monte-Cristo
2787 / 1373 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
01.11.2009, 22:25     Бинарный поиск в массиве #16
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Monte-Cristo, а что возвратит приведенная тобой функция BinSearch в случае, если искомый элемент отсутствует?
Я вставил функцию BinSearch, которую писал год назад, когда еще толком С++ не знал. С++ я учу только полгода.Так что вполне возможны недочеты. Например там лишняя переменная z. Не помню зачем ее вводил, но наверное для вывода кол-ва итераций.
CyBOSSeR
Эксперт C++
2299 / 1669 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.11.2009, 22:33     Бинарный поиск в массиве #17
Monte-Cristo, недочеты, естественно, возможны у всех. Главное их вовремя заметить.
DINAzavR
78 / 78 / 2
Регистрация: 11.06.2011
Сообщений: 335
11.06.2011, 00:47     Бинарный поиск в массиве #18
А как решить эту же задачу, только с добавлением рекурсии?
Fellan
1 / 1 / 0
Регистрация: 01.05.2011
Сообщений: 4
13.06.2011, 17:41     Бинарный поиск в массиве #19
Возможно так, писал в блокноте, сам не компилировал, сделал по функции выше)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
void BinSearch(arr, count, key, 0, count-1) ;//вызов
 
 
void BinSearch(const int* arr, int count, int key, int l, int u) 
{
  if(l <= u) {
    int m = (l + u) / 2;
    if (arr[m] == key) cout<<"find";
    if (arr[m] < key) BinSearch(arr, count, key, m+1, u);
    if (arr[m] > key) BinSearch(arr, count, key, l, m-1);
  }
  else cout<<":(";
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.06.2011, 06:02     Бинарный поиск в массиве
Еще ссылки по теме:

Бинарный (двоичный) поиск по алфавиту в упорядоченном массиве структур - C++
Приветствую товарищей-программистов! Есть массив структур StructWords massiv. struct StructWords { char Word; //другие данные ...

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

Вставить функцию в код по подсчету времени на нахождения ключа в массиве (бинарный поиск) - C++
помогите вставить функцию в код по подсчету времени на нахождения ключа в массиве(бинарный поиск) . вот код #include &lt;stdlib.h&gt; ...

Бинарный поиск - C++
#include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;algorithm&gt; #include &lt;string&gt; #include &lt;vector&gt; using namespace std; ...

Бинарный поиск - C++
Здравствуйте, помогите пожалуйста написать бинарный поиск одного элемента, текст читается из файла. Лабу сдавать в понедельник а я не знаю...


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

Или воспользуйтесь поиском по форуму:
DINAzavR
78 / 78 / 2
Регистрация: 11.06.2011
Сообщений: 335
14.06.2011, 06:02     Бинарный поиск в массиве #20
Спасибо. Теперь все понятно.
Yandex
Объявления
14.06.2011, 06:02     Бинарный поиск в массиве
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru