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

Предположим, у нас есть отсортированный массив. Если нам надо найти в этом массиве элемент, то мы можем искать не тупым перебором, а написать гораздо более рациональный алгоритм (это важно, когда у нас массив очень большой) - алгоритм бинарного поиска. Суть его в том, что мы условно разбиваем массив на две половинки, определяем в какой из половинок должен находиться этот элемент (методом сравнения, элементы то расположены по порядку!), затем найденную половинку делим точно так же на две части и продолжаем поиск уже в ней. И так до тех пор, пока не найдем элемент. Эффект этого метода рассмотрим на примере: пусть у нас в массиве 1 миллион элементов. Что бы найти искомый методом перебора, нам надо перебрать максимум миллион элементов. А если воспользоваться методом бинарного поиска? То нам надо будет перебрать максимум 20 элементов (всего то! чувствуете разницу?), поскольку 2²⁰ это как раз примерно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++ Express Edition", авторское право на который принадлежит корпорации Microsoft..

Последнее обновление ( 21.09.2013 г. )

« След.		Пред. »

Вернуться