Претраживање низа

Претраживањем низа проверава се да ли се одређена вредност налази у низу, односно да ли постоји елемент који задовољава одређени услов и који је његов индекс. За претраживање низа развијени су разни алгоритми, међу којима се највише користе алгоритам линеарног (секвенцијалног) претраживања и алгоритам бинарне претраге. Који ће се од многобројних алгоритама користити, зависи од потребе. Увек би требало примењивати најефикаснији алгоритам претраге - онај који доводи до решења са најмањим бројем поређења вредности у поступку претраге.

Линеарно претраживање

Линеарно претраживање је најједноставније, али често не и најефикасније. Како само име алгоритма наговештава, до резултата се долази упоређивањем сваког елемента низа са траженом вредношћу. То значи да је максимални број поређења једнак броју елемената низа. Погледај следећи видео пре него што започнеш са решавањем задатка

Напиши програм у програмском језику C којим се са стандардног улаза уноси цео број num типа int, проналази први елемент у низу arr који има вредност num и на стандардни излаз исписује његов индекс. Ако у низу не постоји елемент са вредношћу num на стандардни излаз исписује се -1. Нека је у програму низ arr типа int иницијализован са произвољним бројем елемената.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int arr[] = { 3, 6, 8, 12, 4, 9, 7 }, num, ind = -1;
    int n = sizeof(arr) / sizeof(arr[0]);
    scanf("%d", &num);
    for (int i = 0; i < n; i++)
        if (arr[i] == num)
        {
            ind = i;
            break;
        }
    printf("%d", ind);
    return 0;
}

Пошто низ може да има више елемената са траженом вредношћу, програм можеш да модификујеш тако да испише индексе свих елемената који имају вредност num:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int arr[] = { 3, 6, 8, 12, 8, 9, 7, 8 }, num, ind = -1;
    int n = sizeof(arr) / sizeof(arr[0]);
    scanf("%d", &num);
    for (int i = 0; i < n; i++)
        if (arr[i] == num)
        {
            ind = i;
            printf("%d ", ind);
        }
    if (ind == -1)
        printf("%d", ind);
    return 0;
}

Можеш и да модификујеш програм тако да испише број пронађених елемената који имају вредност num:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int arr[] = { 3, 6, 8, 12, 8, 9, 7, 8 }, num, sum = 0;
    int n = sizeof(arr) / sizeof(arr[0]);
    scanf("%d", &num);
    for (int i = 0; i < n; i++)
        if (arr[i] == num)
            sum++;
    if (sum > 0)
        printf("%d", sum);
    else
        printf("-1");
    return 0;
}

Бинарно претраживање

Алгоритам бинарне претраге подразумева претрагу у сортираном низу. У сваком кораку, алгоритам упоређује тражену вредност са вредношћу средишњег члана низа. Ако се вредности подударају, онда се алгоритам завршава јер је средишњи елемент тражени елемент, па је тиме пронађен и његов индекс. У супротном, уколико је тражена вредност мања од вредности средишњег члана, алгоритам се понавља на леви подниз у односу на средишњи елемент. Ако је тражена вредност већа од средишњег члана онда се алгоритам примењује на десни подниз. Претрага се на тај начин понавља све док се не пронађе тражена вредност, односно, док се не установи да тражена вредност не постоји. Погледај следећи видео пре него што започнеш са решавањем задатка.

Напиши програм у програмском језику C којим се са стандардног улаза уноси цео број num типа int, па проналази елемент у низу arr који има вредност num и на стандардни излаз исписује његов индекс. Ако у низу не постоји елемент са вредношћу num, на стандардни излаз исписује се -1. Нека је у програму сортиран низ arr типа int иницијализован са произвољним бројем елемената.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
    int arr[] = { 2, 5, 7, 12, 16, 18, 22, 27, 31, 36 }, num;
    int n = sizeof(arr) / sizeof(arr[0]);
    scanf("%d", &num);
    int levo = 0, sredina, desno = n - 1;
    while (levo <= desno) {
        sredina = (levo + desno) / 2;
        if (arr[sredina] == num)
        {
            printf("%d", sredina);
            return 0;
        }
        if (arr[sredina] < num)
            levo = sredina + 1;
        else
            desno = sredina + 1;
    }
    printf("-1");
    return 0;
}

Можеш приметити да алгоритам бинарне претраге захтева много мање поређења (у односу на алгоритам линеарне претраге), што га чини и много бржим и ефикаснијим. Међутим, алгоритам бинарне претрге захтева сортиран низ на улазу, а у пракси низови података често нису сортирани. На пример, уколико желиш да напишеш програм који проверава да ли ученик има закључену јединицу, низ са закључним оценама ученика вероватно није сортиран, већ су оцене записане оним редом којим су записани предмети у дневнику. У наредним лекцијама научићеш како се сортирају елементи низа у опадајућем или растућем поретку.