Tìm kiếm nhị phân?

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 : Vị trí i mà ai = k hoặc thông báo không tìm thấy k trong dãy. Vị trí của 21 trong dãy là 6 (không tìm thấy 25)

2. Ý tưởng

• Sử dụng tính chất dãy A đã sắp xếp tăng, ta tìm cách thu hẹp nhanh vùng tìm kiếm bằng cách so sánh k với số hạng ở giữa phạm vi tìm kiếm (agiữa), khi đó chỉ xảy ra một trong ba trường hợp:

  • Nếu agiữa= k thì tìm được chỉ số, kết thúc;

  • Nếu agiữa > k thì  việc tìm kiếm thu hẹp chỉ xét từ ađầu (phạm vi) $\to$ agiữa – 1;

  • Nếu agiữa $\to$ acuối (phạm vi).

• Quá trình trên được lặp lại cho đến khi tìm thấy khóa k trên dãy A hoặc phạm vi tìm kiếm bằng rỗng.

3. Xây dựng 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à giá trị khoá k;

• Bước 2: Đầu $\leftarrow$ 1; Cuối $\leftarrow$ N;

• Bước 3: Giữa [(Đầu+Cuối)/2];

• Bước 4: Nếu aGiữa = k thì thông báo chỉ số Giữa, rồi kết thúc;

• Bước 5: Nếu a

• Giữa > k thì đặt Cuối = Giữa – 1 rồi chuyển sang bước 7;

• Bước 6: Đầu $\leftarrow$ Giữa + 1;

• Bước 7: Nếu Đầu > Cuối thì thông báo không tìm thấy khóa k trên dãy, rồi kết thúc;

• Bước 8: Quay lại bước 3.

b) Sơ đồ khối