Thuật toán tìm kiếm nhị phân (Binary Search)

1/ Xác định bài toán
- Input: Dãy A là dãy tăng gồm N số nguyên khác nhau a1, a2, ..., aN và một số nguyên k;
- Output: Chỉ số i mà ai = k hoặc thông báo không có số hạng nào của dãy A có giá trị bằng k.
2/ Thuật toán
a/ Cách liệt kê
Bước 1: Nhập N, các số hạng a1, a2,...,aN và khóa k;
Bước 2: Dau := 1, Cuoi := N;
Bước 3: Giua := [(Dau + Cuoi)/2];
Bước 4: Nếu aGiua = k thì thông báo chỉ số Giua, rồi kết thúc;
Bước 5: Nếu aGiua > k thì đặt Cuoi = Giua - 1, rồi chuyển đến bước 7;
Bước 6: Dau := Giua + 1;
Bước 7: Nếu Dau > Cuoi thì thông báo dãy A không có số hạng có giá trị bằng k, rồi kết thúc;
Bước 8: Quay lại bước 3.