Quay tr l i v i c bài, n u ta bi t r ng các lá bài đã đ
c x p th t , thì ta có th vi t m t phiên b n
ở ạ ớ ỗ
ế
ế ằ
ượ ế
ứ ự
ể ế
ộ
ả
khác findCard, nh ng ch y nhanh h n. Cách t t nh t đ vi t ph
ng th c tìm ki m chia đôi là dùng
ư
ạ
ơ
ố
ấ ể ế
ươ
ứ
ế
cách đ quy, b i vi c chia đôi v b n ch t là mang tính đ quy.
ệ
ở
ệ
ề ả
ấ
ệ
M t m o là vi t m t ph
ng th c có tên
ộ
ẹ
ế
ộ
ươ
ứ
findBisect trong đó nh n vào tham s là hai ch s ,
ậ
ố
ỉ ố low và high,
quy đ nh đo n trong m ng c n đ
c tìm ki m (bao g m c
ị
ạ
ả
ầ
ượ
ế
ồ
ả low và high).
1.
Đ tìm ki m trên m ng, hãy ch n m t ch s gi a
ể
ế
ả
ọ
ộ
ỉ ố ữ low và high (g i nó là
ọ
mid) r i so sánh nó v i lá bài
ồ
ớ
c n tìm.
ầ
2. N u b n đã tìm th y nó thì d ng l i.
ế
ạ
ấ
ừ
ạ
3.
N u lá bài t i
ế
ạ mid cao h n lá bài c n tìm, thì tìm ki m trong kho ng t
ơ
ầ
ế
ả
ừ low đ n
ế mid-1.
4.
N u lá bài t i
ế
ạ mid th p h n lá bài c n tìm, thì tìm ki m trong kho ng t
ấ
ơ
ầ
ế
ả
ừ mid+1 đ n
ế high.
Các b
c 3 và 4 trông gi ng nh ng l i g i đ quy đ n m c đáng ng . Sau đây là toàn b ý t
ng khi
ướ
ố
ữ
ờ ọ ệ
ế
ứ
ờ
ộ
ưở
chuy n thành mã l nh Java:
ể
ệ
public static int
findBisect(Card[] cards, Card card,
int
low,
int
high) {
// CẦN LÀM: một trường hợp cơ sở
int
mid = (high + low) / 2;
int
comp = compareCard(cards[mid], card);
if
(comp == 0) {
return
mid;
}
else if
(comp > 0) {
return
findBisect(cards, card, low, mid-1);
}
else
{
return
findBisect(cards, card, mid+1, high);
}
}
Mã l nh này có ch a ph n c t lõi c a phép tìm ki m chia đôi, song v n thi u m t ph n trong tr ng, đó
ệ
ứ
ầ ố
ủ
ế
ẫ
ế
ộ
ầ
ọ
là lý do mà tôi đã ghi chú “C N LÀM”. Nh đã vi t, ph
ng th c này s l p đ quy mãi mãi n u nh lá
Ầ
ư
ế
ươ
ứ
ẽ ặ
ệ
ế
ư
bài không có trong c . Ta c n m t tr
ng h p c b n đ x lý tình hu ng này.
ỗ
ầ
ộ
ườ
ợ ơ ả
ể ử
ố
N u
ế high nh h n
ỏ ơ low, thì không có lá bài nào gi a chúng, b i v y ta s k t lu n r ng lá bài c n tìm
ữ
ở ậ
ẽ ế
ậ ằ
ầ
không có trong c . N u ta x lý đ
c tr
ng h p đó, thì ph
ng th c s ho t đ ng đúng:
ỗ ế
ử
ượ
ườ
ợ
ươ
ứ ẽ
ạ ộ
public static int
findBisect(Card[] cards, Card card,
int
low,
int
high) {
System.out.println(low +
", "
+ high);
if
(high < low)
return
-1;
int
mid = (high + low) / 2;
int
comp = compareCard(cards[mid], card);
if
(comp == 0) {
return
mid;
}
else if
(comp > 0) {
return
findBisect(cards, card, low, mid-1);
