W tym poście chciałbym opisać sposób zastosowania algorytmu wyszukiwania binarnego.
Wyszukiwanie binarne pozwala na znalezienie szukanego elementu w uporządkowanym zbiorze. Jego działanie opiera się na dzielenie przeszukiwanego zbioru pół. Po czym następuje zawężenie szukanej wartości do kolejnej połówki w zależności od tego, czy szukana zmienna jest większa bądź mniejsza od aktualnej pozycji w buforze. Operacja jest powtarzana do czasu znalezienia szukanej wartości.
Poniżej przykładowy program w języku C:
- #include <stdio.h>
- int binarySearch_GetPosition(int* nums, int numsSize, int target, int* position) {
- int left = 0;
- int right = numsSize;
- int mid = 0;
- while ((right - left) > 1) {
- mid = ((right + left)) / 2;
- if (nums[mid] > target) { right = mid; }
- else { left = mid + 1; }
- }
- if (nums[left-1] == target) {
- *position = left - 1;
- return 1;
- }
- else {
- *position = left;
- }
- return 0;
- }
- int main() {
- int primes[] = { 2, 3, 5, 7, 11, 13, // 0 1 2 3 4 5
- 17, 19, 23, 29, 31, //6 7 8 9 10
- 37, 41, 43, 47, 53, //11 12 13 14 15
- 59, 61, 67, 71, 73, //16 17 18 19 20
- 79, 83, 89, 97 }; //21 22 23 24 25
- int sizeOfValu = (sizeof(primes) / sizeof(int)) - 1;
- int position = 0;
- int findStatus = 0;
- findStatus = binarySearch_GetPosition(&primes[0], sizeof(primes)/sizeof(int), 7, &position);
- if (findStatus == 1)
- {
- printf("Value in array - %d Position - %d", primes[position], position);
- }
- else
- {
- printf("Value NOT FOUND Should be in position - %d", position);
- }
- return 0;
- }
Funkcja przeszukująca tablicę zwraca status wykonanej operacji. W przypadku gdy szukana wartość znajduje się w tablicy zwraca 1 oraz do zmiennej position wpisywany jest indeks szukanej wartości. Gdy nie będzie jej tablicy, funkcja zwróci wartość 0 oraz do zmiennej position zostanie wpisany numer indeksu na którym powinna znajdować się szukana liczba.
