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

@diana92 · Регистрация: 25.10.2009

Студворк — интернет-сервис помощи студентам

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

@Monte-Cristo · 01.11.2009, 21:41

Например так

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 · 01.11.2009, 21:46 **[ТС]**

да типа

только не надо вводить числа в массив, они будут введенны уже

Можно так?

@audiophile · 01.11.2009, 21:46

Или так:

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 · 01.11.2009, 21:46

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 · 01.11.2009, 21:47

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

@Gravity · 01.11.2009, 21:48

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 · 01.11.2009, 22:06 **[ТС]**

Сообщение от 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 · 01.11.2009, 22:12

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 · 01.11.2009, 22:13

Так попробуй:

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 · 01.11.2009, 22:14 **[ТС]**

audiophile , просто мой препод не разрешает применять то,что мы еще не проходиди, а мы только return 0 пока прошли

@audiophile · 01.11.2009, 22:16

Сообщение от diana92

а мы только return 0 пока прошли

Ээээ... Как бы некоторая функция может возвращать любое число, объект... Вы будете проходить их все? 0,1,2,3,...? Вы не так его поняли.

@diana92 · 01.11.2009, 22:17 **[ТС]**

Сообщение от 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 · 01.11.2009, 22:19

Сообщение от 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 · 01.11.2009, 22:19

Вот это скопируй и запусти.

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 · 01.11.2009, 22:25

Сообщение от CyBOSSeR

Monte-Cristo, а что возвратит приведенная тобой функция BinSearch в случае, если искомый элемент отсутствует?

Я вставил функцию BinSearch, которую писал год назад, когда еще толком С++ не знал. С++ я учу только полгода.Так что вполне возможны недочеты. Например там лишняя переменная z. Не помню зачем ее вводил, но наверное для вывода кол-ва итераций.

@CyBOSSeR · 01.11.2009, 22:33

Monte-Cristo, недочеты, естественно, возможны у всех. Главное их вовремя заметить

.

@DINAzavR · 11.06.2011, 00:47

А как решить эту же задачу, только с добавлением рекурсии?

@Fellan · 13.06.2011, 17:41

Возможно так, писал в блокноте, сам не компилировал, сделал по функции выше)

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<<":(";
}

@DINAzavR · 14.06.2011, 06:02

Спасибо. Теперь все понятно.

Новые блоги и статьи Все статьи Все блоги /
Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .	Фото: Daniel Greenwood kumehtar 13.11.2025

@diana92 4 / 4 / 0 Регистрация: 25.10.2009 Сообщений: 36

	Бинарный поиск в массиве 01.11.2009, 21:30. Показов 102659. Ответов 22 Метки нет (Все метки) Помогите нужна программа по поиску числа в массиве (бинарным методом). Очень очень нужно 0

@diana92 4 / 4 / 0 Регистрация: 25.10.2009 Сообщений: 36
	01.11.2009, 21:46 [ТС]
	да типа только не надо вводить числа в массив, они будут введенны уже Можно так? 0

@audiophile 10 / 10 / 2 Регистрация: 01.11.2009 Сообщений: 67
	01.11.2009, 21:47
	diana92, бинарный поиск предполагает, что числа в массиве, где он будет производиться, уже отсортированы по возрастанию! 0

@diana92 4 / 4 / 0 Регистрация: 25.10.2009 Сообщений: 36
	01.11.2009, 22:14 [ТС]
	audiophile , просто мой препод не разрешает применять то,что мы еще не проходиди, а мы только return 0 пока прошли 0

@CyBOSSeR 2348 / 1721 / 149 Регистрация: 06.03.2009 Сообщений: 3,675
	01.11.2009, 22:33
	Monte-Cristo, недочеты, естественно, возможны у всех. Главное их вовремя заметить. 0

@DINAzavR 78 / 78 / 0 Регистрация: 11.06.2011 Сообщений: 335
	11.06.2011, 00:47
	А как решить эту же задачу, только с добавлением рекурсии? 0

@DINAzavR 78 / 78 / 0 Регистрация: 11.06.2011 Сообщений: 335
	14.06.2011, 06:02
	Спасибо. Теперь все понятно. 0