Программирование - это просто
Advertisement
Главная arrow Уроки программирования arrow Уроки Visual C++ arrow Microsoft visual c++ 2008. Урок 13. Метод двоичного (бинарного) поиска.
28.02.2024 г.
Главное меню
Главная
Интернет магазин
Программные продукты
Биржевые роботы
Искусственный интеллект
Математика и информатика
1С:Предприятие
Уроки C#
Уроки Delphi
Уроки программирования
Web-программирование
Дизайн и графика
Компьютер для блондинок
Исходники
Статьи
Платный раздел
Рассказы про компьютеры
Хитрости и секреты
Системный подход
Размышления
Наука для чайников
Друзья сайта
Excel-это не сложно
Все о финансах
.
Microsoft visual c++ 2008. Урок 13. Метод двоичного (бинарного) поиска. Печать E-mail
Автор megabax   
08.12.2011 г.
New Page 1

Microsoft visual c++ 2008. Урок 13. Метод двоичного (бинарного) поиска.

Предположим, у нас есть отсортированный массив. Если нам надо найти в этом массиве элемент, то мы можем искать не тупым перебором, а написать гораздо более рациональный алгоритм (это важно, когда у нас массив очень большой) - алгоритм бинарного поиска. Суть его в том, что мы условно разбиваем массив на две половинки, определяем в какой из половинок должен находиться этот элемент (методом сравнения, элементы то расположены по порядку!),  затем найденную половинку делим точно так же на две части и продолжаем поиск уже в ней. И так до тех пор, пока не найдем элемент. Эффект этого метода рассмотрим на примере: пусть у нас в массиве 1 миллион элементов. Что бы найти искомый методом перебора, нам надо перебрать максимум миллион элементов. А если воспользоваться методом бинарного поиска? То нам надо будет перебрать максимум 20 элементов (всего то! чувствуете разницу?), поскольку 220 это как раз примерно1 миллион. 

А теперь давайте реализуем этот алгоритм на С++:

#include "stdafx.h"

#include <stdio.h>

#include <stdlib.h>  //for atoi

#include <conio.h>

#define eof -1   //Ctrl+Z

#define maxline 10

 

// ввод строки с клавиатуры

int getline(char s[], int lim) {

    int c,i;

    for(i=0; i<lim-1 && (c=getchar())!=eof && c!='\n'; i++) s[i]=c;

    s[i]='\0';

    i++;

    return i;

}

 

//ищет в массиве v[n] элемент x

int binary(int x, int v[], int n) {

    int low,hight,mid;

    low=0;

    hight=n-1;

    while (low<=hight) {

        mid=(low+hight)/2;

        if(x<v[mid]) hight=mid-1;

        else if (x>v[mid]) low=mid+1;

        else return mid;

    }

    return -1;

}

 

 

int _tmain(int argc, _TCHAR* argv[])

{

    int v[maxline]={0,1,3,5,8,9,12,14,18,21};

    int c,i,x;

    char s[maxline];

    do {

        printf("Enter new x ");

        getline(s,maxline);

        x=atoi(s);

        i=binary(x,v,10);

        if (i!=-1) printf("x fount in %d\n",i); else printf("x is not found!\n");

    } while ((c=getchar())!=eof);

    printf("Press any key to continue");

    _getch();  

    return 0;

}

Вот протокол работы программы:

Microsoft visual c++ 2008. Урок 13. Метод двоичного (бинарного) поиска.


Скриншоты, помеченные знаком *, являются цитатами и иллюстрациями   программного продукта "Microsoft Visual C++ Express Edition", авторское право на который принадлежит корпорации Microsoft.. 


 

Последнее обновление ( 21.09.2013 г. )
 
« След.   Пред. »
 
© 2024 Программирование - это просто
Joomla! - свободное программное обеспечение, распространяемое по лицензии GNU/GPL.
Русская локализация © 2005-2008 Joom.Ru - Русский Дом Joomla!
Design by Mamboteam.com | Powered by Mambobanner.de
Я принимаю Яндекс.Деньги