Ҷустуҷӯи дуӣ чӣ гуна кор мекунад ва чаро он алгоритми муҳим аст
Ҷустуҷӯи дуӣ як усули бунёдӣ аст, ки барои самаранок ёфтани як унсур ё як қимати оптималӣ истифода мешавад, вақте ки ҷавоб ``якранг'' рафтор мекунад.
Фарз мекунем, ки мо массиви тартибдодашуда дорем ва мехоҳем мавқеи қимати -ро ёбем, яъне чунин индекси -ро, ки .
Як ҳалли соддалавҳона ин аст, ки массивро аз назар гузаронем:
Ин дар вақти кор мекунад.
Аммо, азбаски массив тартибдодашуда аст, мо метавонем хеле беҳтар кор кунем: ҷустуҷӯи дуиро истифода барем ва вақти гирем: мо як фосилаи -ро нигоҳ медорем, ки ҳатман ҷавобро дар бар мегирад (агар вуҷуд дошта бошад), онро такроран ба ду ним тақсим мекунем ва нимеро, ки ҷавоб дар он буда наметавонад, канор мегузорем.
Ҳоло мо ҷустуҷӯи дуии стандартии итеративиро тавсиф мекунем, ки ҳар гуна индекси -ро бармегардонад, ки , ё агар ҳузур надошта бошад.
Диапазони ҷавобро оғоз мекунем, яъне фосилаи , ки ҷавоб дар он ҷойгир аст (). Дар ибтидо, .
Сипас мо ду ҳолат дорем:
int find_linear(int x) {
for (int i = 1; i <= n; i++) {
if (a[i] == x) {
return i;
}
}
return -1; // агар x дар массив вуҷуд надошта бошад
}
int binary_search_any(int x) {
int l = 1;
int r = n;
while (l < r) {
int m = (l + r) / 2;
if (a[m] < x) {
l = m + 1;
} else {
r = m;
}
}
if (a[l] == x) {
return l;
}
return -1;
}