BT13: Thuật toán tìm kiếm nhị phân (Binary Search)
1. Yêu cầu
Viết chương trình C# sử dụng hàm không đệ quy để tìm kiếm giá trị Khóa trong danh sách các số nguyên đã cho bằng cách sử dụng thuật toán Tìm kiếm nhị phân (Binary Search).
Giải thích:
Đối với tìm kiếm nhị phân, các phần tử trong danh sách phải được sắp xếp theo thứ tự. Trong phương pháp tìm kiếm này, giá trị tìm kiếm (khoá) sẽ được so với phần tử ở giữa của danh sách. Nếu khoá tìm thấy, thì kết thúc và trả về vị trí tìm thấy.
Nếu khóa nhỏ hơn phần tử giữa của danh sách, thì lặp lại quy trình tìm kiếm với danh sách ở bên trái của phần tử giữa.
Nếu khóa lớn hơn phần tử giữa của danh sách, thì lặp lại quy trình trên tìm kiếm với danh sách ở bên phải của phần tử giữa
2. Thuật toán
Start
Declare mảng a , các biến
Read Số phần tử mảng n
Read Các phần từ của mảng và Giá trị tìm kiếm key
Set found = false;
Set first = 0
Set last = n - 1
loop (first<=last)
middle = (first + last) / 2
if (a [middle] <key)
first = middle + 1
else if (a [middle] == key)
{
Print giá trị tìm kiếm và vị trí trong mảng
break;
}
else
last = middle – 1
end loop
if (found == false)
Print "Không tìm thấy giá trị tìm kiếm"
Stop