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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 240, средняя оценка - 4.93
diana92
4 / 4 / 1
Регистрация: 25.10.2009
Сообщений: 36
01.11.2009, 21:30     Бинарный поиск в массиве #1
Помогите нужна программа по поиску числа в массиве (бинарным методом). Очень очень нужно
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Monte-Cristo
 Аватар для Monte-Cristo
2805 / 1370 / 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++
 Аватар для CyBOSSeR
2293 / 1663 / 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
 Аватар для Gravity
556 / 550 / 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++
 Аватар для CyBOSSeR
2293 / 1663 / 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++
 Аватар для CyBOSSeR
2293 / 1663 / 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
 Аватар для Monte-Cristo
2805 / 1370 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
01.11.2009, 22:25     Бинарный поиск в массиве #16
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
Monte-Cristo, а что возвратит приведенная тобой функция BinSearch в случае, если искомый элемент отсутствует?
Я вставил функцию BinSearch, которую писал год назад, когда еще толком С++ не знал. С++ я учу только полгода.Так что вполне возможны недочеты. Например там лишняя переменная z. Не помню зачем ее вводил, но наверное для вывода кол-ва итераций.
CyBOSSeR
Эксперт C++
 Аватар для CyBOSSeR
2293 / 1663 / 86
Регистрация: 06.03.2009
Сообщений: 3,675
01.11.2009, 22:33     Бинарный поиск в массиве #17
Monte-Cristo, недочеты, естественно, возможны у всех. Главное их вовремя заметить.
DINAzavR
77 / 77 / 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++ Бинарный поиск
Поиск числа в двумерном массиве (бинарный поиск) C++
C++ Бинарный (двоичный) поиск по алфавиту в упорядоченном массиве структур

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

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

Текущее время: 21:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru