Написать программу, которая методом бинарного поиска проверяет наличие элемента в упорядоченном по возрастанию массиве.
Данный пример реализации бинарного поиска является не совсем «классическим», но работает при всех входных данных (сколько проверял — не разу не ошибся). Поэтому, буду рад выслушать любую критику.
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include «stdafx.h»
#include <iostream> using namespace std; int main() {setlocale(LC_ALL,«Rus»); int i, a, b, n, c, x; cout<<» Введите количество элементов «; cin>>n; int *mas = new int[n]; cout<<» Введите элементы массива: \n«; for (i=0; i<n; i++) { cout<<i+1<<» элемент:\t«; cin>>mas[i]; } cout<<«Введите искомый элемент «; cin>>x; i=0; a=0; b=n; c=(b/2); while (a<b) { if (x==mas[c]) { i++; break; } if (x<mas[c]) { b=c; c=a+(b—a)/2; } else if (x>mas[c]) { a=c+1; c=a+(b—a)/2; } } if (i==0) cout<<» no «; else cout<<» yes «; //delete []mas; system(«pause>>void»); return 0; } |