Binary search. (2тын хайлт)

Нилээдгүй үр дүнтэй хайлтын арга. Алхам бүрт нийт өгөгдлийн тоо 2 дахин багасана (зураг 1). Гэхдээ зөвхөн эрэмбэлэгдсэн өгөгдлүүд дээр ажиллана.
N -г нийт өгөгдлийн тоо гэж үзвэл:
хамгийн муугаар бодоход log₂(N) +1 удаа шалгалт хийгдэнэ. Харин шугаман хайлтын хувьд хамгийн муу тохиолдолд N удаа шалгалт хийгдэнэ.
Жишээ: нь 1 сая өгөгдөл дундаас хайлт хийнэ гэж үзье. Энэ нөхцөлд хамгийн муугаар бодоход шугаман хайлт нь шалгах үйлдлийг 1сая удаа хийх боломжтой юм. Харин 2тын хайлт ашиглавал хэзээ ч 20с илүү шалгалт хийгдэхгүй.

Source code :
int binSearch(int a[ ], int low, int high, int key)

{

    if(low < high)
    {
        int mid = (low + high) / 2;
        if(a[mid] == key)
            return mid;
        else if(key < a[mid])
            return binSearch(a, low, mid - 1, key);
        else return binSearch(a, mid+1, high, key);
    }
    else return -1;

}

                                           (Зураг 1)

 Зургийг эндээс.

Ойлгомжгүй, эсвэл асуух зүйл байвал холбоо бариарай залуусаа. Мөн буруу, эсвэл дутуу тайлбарлсан зүйл байвал залруулж өгнө үү.