Бинарна претрага је један од најлакших начина за проналажење елемента у низу

Често често програмери, па чак и почетници, суочавају се са чињеницом да постоји скуп бројева у којима је потребно пронаћи одређени број. Ова колекција се зове арраи. И да нађемо прави елемент у њему, има много начина. Али најједноставнији међу њима је бинарна претрага. Који је метод? И како имплементирати бинарну претрагу? Паскал је најједноставније окружење за организовање таквог програма, тако да ћемо га користити за студирање.

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

Дакле, који је принцип ове методе? Одмах је вриједно рећи да бинарна претрага не ради ни у једном низу, већ само у сортираном скупу бројева. На сваком следећем кораку узима се просечни елемент матрице (односи се на број елемента). Ако је жељени број већи од просјека, онда је све што је на лијевој страни, односно мање од просјечног елемента, могуће одбацити и не тражити тамо. Насупрот томе, ако је мање од просека, међу бројевима са десне стране, не можете их потражити. Затим ћемо одабрати нову област за претрагу, где ће средњи елемент читавог поља бити први елемент, а последњи ће остати последњи. Просјечан број новог подручја ће бити ¼ укупног сегмента, односно (задњи елемент + просјечни елемент читавог поља) / 2. Поново се врши иста операција - поређење са просечним бројем поља. Ако је жељена вредност мања од просјечне, одбаците десну страну и урадите исто док се не пронађе овај средњи елемент.

Наравно, најбољи начин да погледамо овај пример је како написати бинарну претрагу. Пасцал овде је погодан за било кога - верзија није важна. Хајде да напишемо једноставан програм.

Имаће низ од 1 до х који се зове "масив", варијабла која означава нижу границу претраге, названа "низ", горња граница под именом "верх", средњи елемент претраге је "средн"; А потребан број је "иск".

Дакле, прво доделите горње и доње границе интервала претраживања:

Низ: = 1;
Верх: = х + 1;

Затим организујемо циклус "док је дно мање од горње границе":

Иако низ <верх - 1 до
Почните

На сваком кораку поделите сегмент за 2:

Средн: = (низ + верх) див 2; {Користите диву функцију јер делимо остатак}

Сваки пут када провјеравамо. Ако је просек једнак жељеном, прекидамо циклус, пошто је жељени елемент већ пронађен:

Иф средн = иск затим пауза;

Ако је средњи елемент низа већи од оног који тражимо, одбацимо леву страну, односно средњи елемент доделимо горњој граници:

Ако массив [средн]> иск онда верх: = средн;

А ако напротив, онда ћемо то доњи лимит:

Други низ: = средн;
Крај;

То је све што ће бити у програму.

Хајде да анализирамо како ће бинарни метод изгледати у пракси. Узмите такав низ: 1, 3, 5, 7, 10, 12, 18 и потражите број 12 у њему.

Укупно, имамо 7 елемената, тако да ће просек бити четврти, његова вриједност 7.

Пошто је 12 веће од 7, елементи 1,3 и 5 се могу одбацити. Затим имамо 4 бројеве, 4/2 без остатка је 2. Дакле, нови средњи елемент ће бити 10.

Пошто је 12 више од 10, одбацимо 7. Само 10, 12 и 18 остају.

Овде је средњи елемент већ 12, ово је потребан број. Задатак је завршен - пронађен је број 12.