Anh (Chị) hãy cho biết kết quả của đoạn lệnh sau là gì?
int BinSearch (char*item,char *table[],int n, int (*Sosanh)(const char*,const char*))
{ int bot = 0, top = n - 1, mid, cmp;
while (bot < top) { mid = (bot + top) / 2;
if ((cmp = Sosanh(item,table[mid])) == 0) return mid;
else if (cmp < 0) top = mid - 1;
else bot = mid + 1;
}
return -1;
}
int main() { char *cities[] = { “Boston”, “London”, “Sydney”, “Tokyo” };
cout << BinSearch (“Sydney”,cities,4,strcmp) << endl;
}
Trả lời:
Đáp án đúng: B
Đoạn chương trình thực hiện tìm kiếm nhị phân (Binary Search) trên một mảng các chuỗi. Hàm `BinSearch` tìm kiếm chuỗi `item` trong mảng `table` có `n` phần tử, sử dụng hàm so sánh `Sosanh`. Trong hàm `main`, mảng `cities` chứa các chuỗi "Boston", "London", "Sydney", "Tokyo". Hàm `BinSearch` được gọi để tìm chuỗi "Sydney" trong mảng `cities` với `n = 4` và hàm so sánh `strcmp`.
Bước thực hiện:
1. `bot = 0`, `top = 3`
2. Vòng lặp `while (bot <= top)`:
* `mid = (0 + 3) / 2 = 1`
* `cmp = strcmp("Sydney", cities[1]) = strcmp("Sydney", "London")`. Vì "Sydney" > "London" nên `cmp > 0`.
* `bot = mid + 1 = 2`
3. Vòng lặp `while (bot <= top)`:
* `mid = (2 + 3) / 2 = 2`
* `cmp = strcmp("Sydney", cities[2]) = strcmp("Sydney", "Sydney") = 0`
* Trả về `mid = 2`
Vậy, chương trình in ra `2`.
Lưu ý: Trong đoạn code gốc, điều kiện vòng lặp while là `bot < top`, nhưng theo logic tìm kiếm nhị phân thông thường, điều kiện nên là `bot <= top`. Tuy nhiên, code đưa ra vẫn hoạt động đúng với test case này, bởi vì khi `bot = top = 2`, giá trị `mid` cũng bằng 2, và `strcmp` sẽ trả về 0, kết thúc vòng lặp và trả về 2. Nếu điều kiện là `bot < top`, thì kết quả sẽ sai. Tuy nhiên, ta cần đánh giá đoạn code đã cho, không phải đoạn code "đúng".