Двійковий пошук
Матеріал з Вікіпедії — вільної енциклопедії.
Двійкóвий пóшук — алгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини (див. двійкове дерево), залежно від результату порівняння.
Трудомісткість алгоритму 1 + log2N.
[ред.] Приклад на C++
int BinarySearch(int A[], int left, int right, int val, int &place)
{
int mid; //middle point between left and right
int found; //1- value found; 0- value still not found
int found=0;
while((left<=right) && (!found)){
mid=(left+right)/2; // compute middle point
// check value against maiddle point and adjust bounds accordingly.
if(val==A[mid]) {
place=mid;
found=1;
}
else if (val<A[mid]) right=mid-1;
else left=mid+1;
}
return (found);
}

