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

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

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

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

@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

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

Новые блоги и статьи Все статьи Все блоги /
sshd restrictions, ssh access limitations jigi33 26.03.2025 sshd restrictions \| ssh access limitations рестрикции доступа на сервер sshd статья: https:/ / www. golinuxcloud. com/ restrict-allow-ssh-certain-users-groups-rhel	Компиляция C++ с Clang API NullReferenced 24.03.2025 Компиляторы обычно воспринимаются как черные ящики, которые превращают исходный код в исполняемые файлы. Мы запускаем компилятор командой в терминале, и вуаля — получаем бинарник. Но что если нужно. . .	Многопоточное программирование в C#: Класс Thread UnmanagedCoder 24.03.2025 Когда запускается приложение на компьютере, операционная система создаёт для него процесс - виртуальное адресное пространство. В C# этот процесс изначально получает один поток выполнения — главный. . .	SwiftUI Data Flow: Передача данных между представлениями mobDevWorks 23.03.2025 При первом знакомстве со SwiftUI кажется, что фреймворк предлагает избыточное количество механизмов для передачи данных: @State, @Binding, @StateObject, @ObservedObject, @EnvironmentObject и другие. . . .	Моки в Java: Сравниваем Mockito, EasyMock, JMockit Javaican 23.03.2025 Как протестировать класс, который зависит от других сложных компонентов, таких как базы данных, веб-сервисы или другие классы, с которыми и так непросто работать в тестовом окружении? Для этого и. . .
Архитектурные паттерны микросервисов: ТОП-10 шаблонов ArchitectMsa 22.03.2025 Популярность микросервисной архитектуры объясняется множеством важных преимуществ. К примеру, она позволяет командам разработчиков работать независимо друг от друга, используя различные технологии и. . .	Оптимизация рендеринга в Unity: Сортировка миллиона спрайтов GameUnited 22.03.2025 Помните, когда наличие сотни спрайтов в игре приводило к существенному падению производительности? Время таких ограничений уходит в прошлое. Сегодня геймдев сталкивается с задачами совершенно иного. . .	Образование и практика Igor3D 21.03.2025 Добрый день А вот каково качество/ эффективность ВУЗовского образования? Аналитическая геометрия изучается в первом семестре и считается довольно легким курсом, что вполне справедливо. Ну хорошо,. . .	Lazarus. Таблица с объединением ячеек. Massaraksh7 21.03.2025 Понадобилась представление на экране таблицы с объединёнными ячейками. И не одной, а штук триста, и все разные. На Delphi я использовал для этих целей TStringGrid, и то, кривовато получалось. А в. . .	Async/await в Swift: Асинхронное программирование в iOS mobDevWorks 20.03.2025 Асинхронное программирование долго было одной из самых сложных задач для разработчиков iOS. В течение многих лет мы сражались с замыканиями, диспетчеризацией очередей и обратными вызовами, чтобы. . .

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

	Бинарный поиск в массиве 01.11.2009, 21:30. Показов 102046. Ответов 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

@audiophile 10 / 10 / 2 Регистрация: 01.11.2009 Сообщений: 67
	01.11.2009, 22:16
	Сообщение от diana92 а мы только return 0 пока прошли Ээээ... Как бы некоторая функция может возвращать любое число, объект... Вы будете проходить их все? 0,1,2,3,...? Вы не так его поняли. 0

@Monte-Cristo 2816 / 1408 / 107 Регистрация: 07.03.2009 Сообщений: 4,446
	01.11.2009, 22:25
	Сообщение от CyBOSSeR Monte-Cristo, а что возвратит приведенная тобой функция BinSearch в случае, если искомый элемент отсутствует? Я вставил функцию BinSearch, которую писал год назад, когда еще толком С++ не знал. С++ я учу только полгода.Так что вполне возможны недочеты. Например там лишняя переменная z. Не помню зачем ее вводил, но наверное для вывода кол-ва итераций. 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