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

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

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

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

@Monte-Cristo · 01.11.2009, 21:41

Например так

C++

#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++

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.
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

#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++

#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++

#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++

#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++

#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++

#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++

#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++

#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++

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

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

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

@diana92 4 / 4 / 0 Регистрация: 25.10.2009 Сообщений: 36
		1
	Бинарный поиск в массиве 01.11.2009, 21:30. Показов 99971. Ответов 22 Метки нет (Все метки) Помогите нужна программа по поиску числа в массиве (бинарным методом). Очень очень нужно 0

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

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

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

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

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

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

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