Giáo trình môn Công nghệ phần mềm (Phần 2)

Ta sè chọn m là vị trí giữa (nếu n lẻ) đế cho V[l.m - 1] và V[m + 1.11] có kích thước bàng nhau, hoặc chọn ni sao cho chúng hơn kém nhau một phán tủ.

Khi đó kích thước của các vectơ thuộc dày Vi, v2,., vk sè lần lượt được chia đòi tại mỗi bước : n, n/2,., n/2k* \

Như vậy, sè có tối đa [ log2n] vectơ con khác rồng.

Ví dụ : nếu n = 9000, số vectơ con khác rồng tối đa sè là 13, vì 213 = 8192

Xây dựng thuật toán :

Sau một sổ bước, ta có vectơ con V[inf. sup] sao cho :

V[l.inf -1] < phántủ < V[sup + 1.11]

Xảy ra hai trường hợp :

• inf > sup (inf = sup + 1)

(V[l.inf-1] < phantu < V[sup+l.n], mf = sup+1) => (phản tu Ễ V, kết thúc)

. inf < sup : m = (inf + sup) div 2

kin đó ta CÓ V[inf.m - 1] < V[m] < V[m + l.sup]

Tồn tại 3 khả núng như sau :

• Phản tủ = V[m] : kết thúc, phan tử G V

. Phần tủ < V[m] : tiếp tục tim kiếm trong V[inf.m - 1]

lấy sup := m - 1 đê có lại khảng định phần tu < V[sup + l.m]

. Phần tủ > V[m] : tiếp tục tim kiếm trong V[m + l .sup] lấy inf := m + 1 đế có lại khảng định V[l.inf - 1] < phần tu

Như vậy cả hai trường hợp : V[l.inf - 1] < phần tủ < V[sup + 1.11]

Khỏi đầu, láu inf := 1 và sup := n