Binary Search (Tìm ki m nh fân)ế ị
Thu tậ toán tìm ki mế nhị fân sử d ngụ kĩ
thu tậ chia để trị để tìm ki mế.
Đ uầ tiên, f nầ tử tìm ki mế đ cượ so sánh
v iớ ph nầ tử gi aữ c aủ list.
N uế f nầ tử tìm ki mế bé hơn ph nầ tử gi aữ,
gi iớ h nạ tìm ki mệ l iạ về n aử đ uầ c aủ list.
N uế không, tìm ki m nếaử sau c aủ list.
Binary Search
Tìm ki mế nhị fân là 1 kỹ thu tậ m nhạ đáng
kinh ng cạ để tìm ki mế trong 1 list đã đ cượ
s pắ x pế.
Nó quen thu cộ v iớ m iọ ng iườ sử d ngụ
danh bạ đi nệ tho iạ.
Minh họa
Tìm ki mế v iớ key = 78:
1 3 5 6 10 11 14 25 26 40 41 78
- (Xem hình minh ho trong slide ti ng anh)ạ ế
- 4 phép toán c n thi t đ tìm ra ph n t fù ầ ế ể ầ ử
h p.ợ
- Th tính xem ph i dùng bao nhiêu phép ử ả
toán n u s d ng tìm ki m tu n t ?ế ử ụ ế ầ ự
Ví dụ
Đ uầ tiên so sánh 78 v iớ f nầ tử gi aữ c aủ
list L[5] là 11.
78 > 11. Vì v yậ ta gi iớ h nạ l iạ tìm ki mế
L[6……11] như hình minh hoạ.
Binary Search Code
// target là số c nầ tìm, size là kích th cướ list
Int binSearch (int List[], int Target, int Size) {
int Mid,
Lo = 0,
Hi = Size –1;
while( Lo <= Hi ) {
Mid = (Lo + Hi) / 2;
if( List[Mid] == Target )
return Mid;
else if( Target < List[Mid] )
Hi = Mid –1;
else
Lo = Mid + 1;
}
return -1;
}