Алгоритм двоичного поиска на C++

Алгоритм двоичного поиска на C++


#include "stdafx.h"
#include <iostream>
using namespace std;

int BinarySearch(int massiv[], int size, int key)
{
int left=0, right=size, mid;
while (left<=right)
{
mid=left+(right-left)/2;
if (key<massiv[mid]) right=mid-1; else if (key>massiv[mid]) left=mid+1;
else return mid;
}
return -1;
}

void main()
{
setlocale(LC_ALL,"Rus");
int key, i, size;
int *massiv;
cout<<"Введите размер массива"<<endl; cin>>size;
massiv=new int [size];
cout<<"Введите поисковой запрос"<<endl; cin>>key;
cout<<"Инициализация массива ";
for (i=0; i<size; i++)
{
massiv[i]=i+1;
cout<<massiv[i]<<" ";
}
if (BinarySearch(massiv, size, key)==-1)
{
cout<<"Элемент не найден "<<endl;
}
else
{
cout<<"Элемент найден: "<<BinarySearch(massiv, size, key)+1<<endl;
}
delete[] massiv;
system("pause");
}

Результат работы алгоритма двоичного поиска на C++

Алгоритм двоичного поиска на C++


Алгоритма бинарного поиска в заданном в диапазоне на C++


#include "stdafx.h"
#include <iostream>
using namespace std;

int BinarySearch(int massiv[], int size, int key)
{
int left=0, right=size, mid;
while (left<=right)
{
mid=left+(right-left)/2;
if (key<massiv[mid]) right=mid-1; else if (key>massiv[mid]) left=mid+1;
else return mid;
}
return -1;
}

int BinarySearchBetween(int massiv[], int size, int key, int min, int max)
{
int mid;
while (min<=max)
{
mid=(min+max)/2;
if (key==massiv[mid]) return mid;
else if (key<massiv[mid]) max=mid-1;
else return min=mid+1;
}
return -1;
}

void main()
{
setlocale(LC_ALL,"Rus");

int key, i, size, min, max;
int *massiv;
cout<<"Введите размер массива"<<endl; cin>>size;
cout<<"Введите минимальное значение"<<endl; cin>>min;
cout<<"Введите максимальное значение"<<endl; cin>>max;
massiv=new int [size];
cout<<"Введите поисковой запрос"<<endl; cin>>key;
cout<<"Инициализация массива ";
for (i=0; i<size; i++)
{
massiv[i]=i+1;
cout<<massiv[i]<<" ";
}
if (BinarySearchBetween(massiv, size, key, min, max)==-1)
{
cout<<"Элемент не найден "<<endl;
}
else
{
cout<<"Элемент найден: "<<BinarySearch(massiv, size, key)+1<<endl;
}
system("pause");
}

Результат работы алгоритма бинарного поиска в заданном в диапазоне на C++

Алгоритм бинарного поиска на C++

Замечание

Алгоритм двоичного поиска основан на методе дихотомии и применяется для отсортированных данных.

Leave a Reply

Ваш e-mail не будет опубликован.