//
you're reading...
01 - Chủ đề thuật toán

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 đôi một 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. Ý tưởng:


Sử dụng tính chất dãy A là dãy tăng, ta tìm cách thu hẹp nhanh phạm vi tìm kiếm sau mỗi lần so sánh khoá với số hạng được chọn. Để làm điều đó, ta chọn số hạng aGiua ở “giữa dãy” để so sánh với k, trong đó Giua = .
Khi đó, chỉ xảy ra một trong ba trường hợp sau:
– Nếu aGiua = k thì Giua là chỉ số cần tìm. Việc tìm kiếm kết thúc.
– Nếu aGiua > k thì do dãy A là dãy đã được sắp xếp nên việc tìm kiếm tiếp theo chỉ xét trên dãy a1, a2,…, aGiua–1 (phạm vi tìm kiếm mới bằng khoảng một nửa phạm vi tìm kiếm trước đó).
– Nếu aGiua < k thì thực hiện tìm kiếm trên dãy aGiua+1, aGiua+2,…, aN.
Quá trình trên sẽ được lặp lại một số lần cho đến khi hoặc đã tìm thấy khoá k trong dãy A hoặc phạm vi tìm kiếm bằng rỗng.


3. 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à khoá 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.


Ghi chú:
Tuỳ thuộc aGiua > k hoặc aGiua < k mà chỉ số đầu hoặc chỉ số cuối của dãy ở bước tìm kiếm tiếp theo sẽ thay đổi. Để thực hiện điều đó, trong thuật toán chỉ sử dụng các biến nguyên tương ứng Dau và Cuoi có giá trị khởi tạo Dau = 1 và Cuoi = N.


Lưu đồ

luu do tim kiem nhi phan

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Tám 2015
H B T N S B C
« Th1   Th9 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Thống kê

  • 210,510 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: