Void main()
{ unsigned N; // кількість елементів у вихідному масиві
int sample; // зразок для пошуку
int k = -1; // результат пошуку :
// k = -1, якщо елемент не знайдений,
// якщо k >= 0, то k – номер першого елемента в масиві, // співпадаючого зі зразком
printf("Розмір масиву N = "); scanf("%u",&N);
int* A = new int[N]; // створення робочого масиву
printf("Введіть елементи масиву: \n");
for(k=0; k<N; k++) scanf("%d",&a[k]);
printf("Зразок для пошуку = "); scanf ("%d", &sample);
for (int i=0; i<N; i++)
// послідовний перегляд всіх елементів масиву
{ if (A[i]==sample) { k = i; break; }
}
if (k>=0) printf("Пошук успішний. Збіг з елементом %d.\n", k);
else printf("Зразок у масиві відсутній \n");
}
Протокол роботи програми:
Розмір масиву N = 6
Введіть елементи масиву:
4 67 8 14 78 9
Зразок для пошуку = 78
Пошук успішний. Збіг з елементом 5.
Алгоритм бінарного пошуку
На практиці досить часто проводиться пошук у масиві, елементи якого впорядковані за деяким критерієм. Для пошуку в упорядкованих масивах застосовують алгоритми більш ефективні, ніж алгоритм простого перебору. Один з них - метод бінарного пошуку.
Суть методу бінарного пошуку полягає в наступному. Будемо вважати, що масив впорядкований по зростанню. Позначимо як s зразок для пошуку.
1. Покласти bot = 0, top = N-1.
2. Обчислити m = bot+(top-bot)/2.
3. Якщо s == A[m] , то процес завершити.
4. Якщо s < A[m], то покласти top = m.
Якщо ні, то покласти bot = m.
Перейти до п. 2.
Нижче наведений текст програми бінарного пошуку. Передбачається, що масив є упорядкованим по зростанню. У програму додані оператори виведення поточних значень змінних top, bot і m. Крім того, змінна n_test (кількість кроків) дозволяє оцінити ефективність цього алгоритму.
// Приклад 2
#include <syst.h>
Yandex.RTB R-A-252273-3- Запоріжжя знту 2008
- Глава 1
- 1.1. Історія та сучасність
- 1.2. Загальна структура програми. Два простих приклади
- Void main()
- Void main()
- Глава 2 Об’єкти та ідентифікатори
- 2.1. Об'єкти та їхні атрибути
- 2.2. Алфавіт мови та лексеми
- 2.3. Ідентифікатори
- Void main() // (рівень 0)
- 2.4. Вправи
- Глава 3
- 3.1. Поняття виразу. Вирази Lvalue та Rvalue
- 3.2. Операції. Пріоритети та асоціативність
- Void main()
- Void main()
- Void main()
- 3.3. Вправи
- Глава 4
- 4.1. Види операторів
- 4.2. Стандартні оператори
- If (лв) опер_1; [ else опер_2; ]
- Void main()
- If (лв1) опер_1;
- Void main()
- Void main()
- Void main()
- Void main()
- Void main()
- 4.3. Оголошення змінних та ініціалізація
- Int number(125);
- Int number(125);
- 4.4. Константи і константні об'єкти
- Void main()
- 4.5. Вправи
- Глава 5
- 5.1. Типи та їхні різновиди
- 5.2. Службове слово void
- Int a[small], a[large];
- 5.4. Перетворення типів
- 5.5. Вправи
- Void main()
- Глава 6 покажчики і посилання
- 6.1. Покажчики
- Void main()
- Void strcpy(char* s1, char* s2)
- Void* pv;
- 6.2. Посилання
- 6.3 Вправи
- Void main()
- Глава 7 масиви і динамічні об'єкти
- 7.1. Масиви
- Void main()
- 7.2. Рядки символів
- Int strlen(char* s);
- Int strcmp(char* s1, char* s2);
- Int len(char *s)
- 7.3. Динамічні об'єкти й масиви
- Void main()
- Void main()
- Void main()
- Void main()
- 7.4. Вправи
- Глава 8 функції та процедури
- 8.1. Загальні відомості
- Void main()
- Void c_mul(double a_re, double a_im,
- Void swap1(long *px, long *py)
- Void swap2(long &X, long &y)
- Void main()
- Int fun(int, float*, double&);
- Void fun(int n)
- Void main()
- Void swap(int& a, int& b)
- 8.2. Функція main
- Void або int main(int n, char** p, char** q);
- Void main(int n, char** p, char** q)
- 8.3. Функції зі змінною кількістю параметрів
- Void main()
- 8.4. Покажчики на функції
- Int (*pf[3])(float X, float y);
- Void main()
- 8.5. Функції з шаблонами
- Void swap(string& s1, string& s2)
- Void main()
- Inline t abs(t X)
- Void create(type* &a, int n)
- Void del(type* &a)
- 8.6. Вправи
- Глава 9 консольне вВедення / вИведення
- 9.1. Засоби бібліотеки с
- Void main()
- Void main()
- Void main()
- 9.2. Використання потоків
- Void main()
- Void main()
- 9.3. Вправи
- Глава 10 операції з файлами
- 10.1. Види файлів і режими роботи з ними
- 10.2. Бібліотека с
- Void fprint(file* f, &X)
- Void rewind(file* f);
- Void main()
- Void main(int n, char** f)
- Void main(int n, char** fnam)
- 10.3. Застосування потоків
- Ifstream fin;
- Void open(char* filename, int mode, int access);
- Ifstream fin("a.Dat");
- Void main()
- Ifstream fa("a.Dat");
- If (fa.Eof()) break;
- Void main(int n, char** fnam)
- Void main(int n, char** f)
- Ifstream fa(f[1]);
- Void main(int n, char** fnam)
- Void main()
- Ifstream in("example.Cpp");
- Void main()
- Ifstream in("name.Dat",ios::binary);
- Void main()
- Ifstream fa("a.Dat");
- Int descr(fstr& f)
- Void main()
- Ifstream ina(infa);
- Ifstream inb(infb);
- 10.4. Вправи
- Глава 11 компіляція програми. Директиви і макроси
- 11.1. Фази компіляції
- 11.2. Директиви режиму компіляції
- 11.3. Директиви препроцесора
- 11.4. Вправи
- Глава 12 змішане програмування. Використання ассемблерного коду
- 12.1. Засоби використання асемблера
- Void main()
- 12.2. Вправи
- Глава 13 програмна реалізація алгоритмів
- 13.1. Алгоритм Евкліда пошуку найбільшого загального дільника двох цілих чисел
- 13.2. Обчислення факторіала
- 13.3. Пошук простих чисел. Решето Ератосфена
- Void main()
- 13.4. Генерація підмножин
- Void main()
- 13.5. Сортування масивів
- Void main()
- Void main()
- Int flag;
- 13.6. Пошук у масиві
- Void main()
- Void main()
- 13.7. Операції з матрицями
- Void ObrMatr (double** a, double** b, unsigned n )
- Void Minv(double** a, double** b, unsigned n )
- Void Gauss(double** a, double* b, double* X, unsigned n)
- 13.8. Лінійна інтерполяція даних
- 13.9. Лінійна апроксимація
- Void linappr(int n, double* X, double* y, double& a0, double& a1)
- 13.10. Розв’язування нелінійних рівнянь
- Void Bisec(funx f, double a, double b, double eps, double& X)
- Void Bisec(funx f, double a, double b,
- Void main()
- 13.11. Пошук заданої послідовності символів у файлі
- Void push(char* s, int n, char X)
- Void main()
- 13.12. Вправи
- Глава 14 створення й використання бібліотечних модулів. Модуль syst.H
- 14.1. Створення бібліотечних модулів
- 14.2. Модуль syst.H
- 14.3. Системні функції та макрооперації
- Void runtimer();
- Void main()
- Void runstimer();
- Void main()
- Void swp(Type& a, Type& b);
- Void main()
- Int cmp(int nx, int ny, Type* X, Type* y);
- Void errhalt(bool ex, char* mes);
- Void errhalt(bool ex, char* mes, file* f);
- 14.4. Операції введення/виведення
- Void flushkey();
- Void main()
- Int getyes();
- Void main()
- Void main()
- Int weight(type X);
- Void main()
- Int hamdist(Type a, Type b)
- 14.6. Спеціальні класи. Клас Spline для інтерполяції даних сплайнами
- Void main()
- 14.7. Вправи
- Глава 15 графІчне виведення. Модуль rgraph.H
- 15.1. Модуль rgraph.H. Загальні відомості
- 15.2. Глобальні змінні й константи
- 15.3. Класи й покажчики на функції
- 15.4. Функції й процедури класів
- Void main()
- Void main()
- Void main()
- Void main()
- 15.7. Вправи
- Глава 16 Життєвий цикл програмного продукту. Питання стилю запису програм
- 16.1. Життєвий цикл програми
- Int n, alfa, col;
- Void draw();
- Void rotate(int delta);
- 16.3. Вправи
- Література