Учебник. К.Ю Поляков, Е.А. Ерёмин. Информатика. 11 класс. Углублённый уровень. §65 Двоичный поиск
Задача A. Двоичный поиск
Реализуйте алгоритм бинарного поиска.
PASCAL
function BinSearch(v:array of longint; l,r,key:longint):boolean;
var m:longint;
begin
repeat
m := l + (r - l) div 2;
if v[m] < key then l := m+1;
if v[m] > key then r := m-1;
until (l>=r) or (v[m] = key);
if l=r
then BinSearch := v[l] = key
else BinSearch := v[m] = key;
end;
var m,v:array of longint;
i,n,k:longint;
begin
readln(n,k);
SetLength(m,n);
SetLength(v,k);
for i:=0 to n-1 do read(m[i]);
for i:=0 to k-1 do read(v[i]);
for i:=0 to k-1 do
if BinSearch(m,0,n-1,v[i]) then writeln('YES') else writeln('NO');
end.
C++
#include [iosream]
using namespace std;
bool BinSearch(int *vect, int l, int r, int key)
{
int m;
do {
m = l + (r - l) / 2;
if (vect[m] < key) l = m+1;
if (vect[m] > key) r = m-1;
} while (!(l>=r || vect[m] == key));
if (l==r) return vect[l] == key;
else return vect[m] == key;
}
int main()
{
int i,n,k;
int *m,*v;
ifstream fin("input.txt");
ofstream fout("output.txt");
fin >> n >> k;
m = new int[n];
v = new int[k];
for (i=0; i < n; i++) fin >> m[i];
for (i=0; i < k; i++) fin >> v[i];
fin.close();
for (i=0; i < k; i++)
if (BinSearch(m,0,n-1,v[i])) {fout << "YES" <
delete [] m;
delete [] v;
fout.close();
return 0;
}