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

Riddik

Дата 6.2.2009, 16:51 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 598
Регистрация: 2.12.2006

Репутация: нет
Всего: нет

Прошу оценить этот алгоритм бинарного поиска в массиве.
Не очень ли он туп и не оптимизирован?
Других алгоритмов бинарного поиска не видел, и до этого никогда не сталкивался с ними. Поэтому, сильно не смейтесь, пожалуйста. Это мой первый алгоритм двоичного поиска, никуда не подсматривал, примеров не видел.

Код


//Бинарный поиск в челочисленном массиве отсортированном по возрастанию

#include <iostream>

using namespace std;

int main()
{
    const short cm=100;      //число элементов массива
    int mas[cm];                //массив целочисленных переменных
    for(int i=0; i<cm; i++)            //заполнения массива целыми числами от 0 до cm
    {
        mas[i]=i;
    }
    int posk;
    int x=cm/2, vr=cm;
        i=0;
    for(;;)
    {
        x=cm/2;          //в x помещается номер среднего элемента массива
        vr=cm;             //в vr помещается число элементов массива
        i=0;             //в i помещается номер нулевого элемента массива 
        cin>>posk;    
        if((posk<0)||(posk>(cm-1))) break; 
        for(;;)
        {
        
            if(posk==mas[x]) break;     //если элемент найден, выход из цикла
            if(posk<mas[x])
            {
                vr=x;     //верхний элемент списка ограничивается vr
                x=(x-i)/2; 
                x+=i;   //в x снова помещается номер среднего элемента слдеующего списка
                continue;
            }
            if(posk>mas[x])
            {
                i=x;   //нижний элемент списка ограничивается i
                x=(vr-i)/2;  
                x+=i;   //в x снова помещается номер среднего элемента слдеующего списка
                    
            }
        
        }
        cout<<endl<<"Nomer elementa: "<<x<<endl;
    }
    
    return 0;
}

bsa

Дата 6.2.2009, 17:22 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Riddik, это программа, реализующая алгоритм. А алгоритмы отображаются иначе, например, блок-схемами.

Для начала могу сказать, что не ожидал увидеть вложенные циклы. Бинарный поиск - поиск делением пополам. Т.е. у тебя есть некий диапазон отсортированных по возрастанию (можно по убыванию, но тогда "больше" и "меньше" нужно поменять местами) значений и есть то, что ты ищешь (итого: 3 параметра):
0. если диапазон пуст - выходишь, так как не нашел
1. берешь значение из середины диапазона
2. сравниваешь его с искомым
3. если оно равно, то выходишь - нашел
4. если меньше, то переходишь на п. 0 с диапазоном от начала до середины (невключительно)
5. если больше, то переходишь на п. 0 с диапазоном от середины (невключительно) до конца.

Алгоритм описан, например, тут: http://algolist.manual.ru/search/bin_search.php

Это сообщение отредактировал(а) bsa - 6.2.2009, 17:23

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

Riddik

Дата 6.2.2009, 17:54 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 598
Регистрация: 2.12.2006

Репутация: нет
Всего: нет

Спасибо за ссылку и за комментарий))

Вложенный цикл просто потому, чтобы можно было пользователю производить поиск столько, сколько он хочет. А сам поиск в программе реализован одним циклом.
Судя по вашей схеме, почти то же самое я и сделал))

Добавлено через 8 минут и 5 секунд
только не так изящно)

Riddik

Дата 6.2.2009, 18:12 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 598
Регистрация: 2.12.2006

Репутация: нет
Всего: нет

Проще

Код


        vg=cm;             
        ng=0;             
        cin>>posk;    
        if((posk<0)||(posk>(cm-1))) return 0; 
        for(;;)
        {
        
            x=(vg+ng)/2;
            if(posk==mas[x]) break;    
            if(posk<mas[x]) vg=--x;
            else if(posk>mas[x]) ng=++x;                    
        
        }
        cout<<endl<<"Nomer elementa: "<<x<<endl;

Это сообщение отредактировал(а) Riddik - 6.2.2009, 18:17

bsa

Дата 6.2.2009, 18:33 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Модератор
Сообщений: 9185
Регистрация: 6.4.2006
Где: Москва, Россия

Репутация: 85
Всего: 196

Код

else if(posk>mas[x]) ng=++x

Тут условие лишнее, так как уже все остальные варианты отброшены.

--------------------

Правильно заданный вопрос - половина ответа
Отзывы о работе модератора.

math64

Дата 6.2.2009, 19:09 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2505
Регистрация: 12.4.2007

Репутация: 12
Всего: 72

Код


//Условие выхода должно быть таким:
if((posk<mas[0])||(posk>mas[cm-1]))
  return 0;
// ng - минимальный  индекс
// vg - максимальный  индекс + 1
int ng, vg, x;
for(ng = 0, vg= cm; ng < vg;)
{
  x = (ng + vg) / 2;
  if(posk == mas[x])
    break;    
  if(posk < mas[x])
    vg = x; // в mas[x-1] может быть искомое значение
  else
    ng = ++x;                    
}
if (ng < vg)
   cout << "Номер элемента:" << x << endl;
else
  cout << "Элемент не найден" << endl;

Есть уже готовые реализации в стандартной библиотеке:

Код


void *  bsearch(const void * key, const void * base,
                          size_t nelem, size_t width,
                          int (*fcmp)(const void *, const void *));

Riddik

Дата 6.2.2009, 23:06 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 598
Регистрация: 2.12.2006

Репутация: нет
Всего: нет

bsa, да, я потом исправил, спасибо)

math64, спасибо, буду знать)))

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »