В этой статье поговорим о поиске. Рассмотрим двоичный (бинарный) поиск. Будет представлен его алгоритм, а также пример программы, реализующей поиск элемента в массиве. Разработку будем вести на языке программирования Си.
Перед поиском исходная последовательность должна быть обязательно отсортирована!
Итак, идея двоичного поиска состоит в следующем: искомый элемент сравнивается со средним элементом последовательности. Если значение аргумента поиска меньше среднего элемента, то исходной последовательностью считается массив элементов от 1 до N/2, если значение аргумента поиска больше среднего элемента, то исходной считаем последовательность от N/2 до N. Далее, для новой последовательности этот процесс повторяется. Продолжаем деление пополам интервала поиска до тех пор, пока не будет найден искомый элемент или длина интервала поиска не станет равна единице.
Приведем реализацию алгоритма на языке Си. Функция int binarysearch(int a, int mass[], int n) в качестве аргументов принимает: искомый элемент, указатель на массив элементов и число элементов в этом массиве. В случае успешного поиска binarysearch возвращает позицию искомого элемента в массиве, если аргумент поиска отсутствует в последовательности элементов, то функция возвратит -1.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
int binarysearch(int a, int mass[], int n) { int low, high, middle; low = 0; high = n - 1; while (low <= high) { middle = (low + high) / 2; if (a < mass[middle]) high = middle - 1; else if (a > mass[middle]) low = middle + 1; else return middle; } return -1; } |
Теперь приведем пример консольной программы, которая производит двоичный поиск в массиве элементов длиной N. Для сортировки последовательности используется метод сортировки вставками.
|
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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
#include <stdio.h> #include <malloc.h> #include <conio.h> int binarysearch(int a, int mass[], int n); void InsertionSort(int n, int mass[]); int main() { //ввод N int N, a; printf("Input N: "); scanf_s("%d", &N); //выделение памяти под массив int* mass; mass = (int *)malloc(N * sizeof(int)); //ввод элементов массива printf("Input the array elements:\n"); for (int i = 0; i < N; i++) scanf_s("%d", &mass[i]); //сортировка вставками InsertionSort(N, mass); //вывод отсортированного массива на экран printf("Sorted array:\n"); for (int i = 0; i < N; i++) printf("%d ", mass[i]); printf("\n"); //ввод искомого элемента printf("Input variable 'a' for search: "); scanf_s("%d", &a); int k; //двоичный поиск k = binarysearch(a, mass, N); if (k != -1) { printf("The index of the element is %d\n", k); } else printf("The element isn't found!\n"); //освобождение памяти free(mass); _getch(); return 0; } int binarysearch(int a, int mass[], int n) { int low, high, middle; low = 0; high = n - 1; while (low <= high) { middle = (low + high) / 2; if (a < mass[middle]) high = middle - 1; else if (a > mass[middle]) low = middle + 1; else return middle; } return -1; } //сортировка вставками void InsertionSort(int n, int mass[]) { int newElement, location; for (int i = 1; i < n; i++) { newElement = mass[i]; location = i - 1; while (location >= 0 && mass[location] > newElement) { mass[location + 1] = mass[location]; location = location - 1; } mass[location + 1] = newElement; } } |
Демонстрация работы программы представлена на скриншоте ниже:
Если вы желаете скачать исходник программы, то нажмите на кнопку:
Скачать исходник
Посмотрите также, как реализуется алгоритм двоичного (бинарного) поиска на С++.
Поделиться в соц. сетях: