Двійковий пошук

Матеріал з Вікіпедії — вільної енциклопедії.

Двійкóвий пóшукалгоритм знаходження заданого значення у впорядкованому масиві, який полягає у порівнянні серединного елемента масиву з шуканим значенням, і повторенням алгоритму для тієї або іншої половини (див. двійкове дерево), залежно від результату порівняння.

Трудомісткість алгоритму 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);
}