Top Ad unit 728 × 90

Latest news

recent

Tìm kiếm nhị phân (Binary search)

Tìm kiếm nhị phân là thuật toán tìm kiếm chỉ làm việc trên dữ liệu đầu vào là một tập hợp đã được sắp xếp (sorted lists hay arrays). Nó thực hiện việc tìm vị trí trung tâm, thông qua phép so sánh giữa giá trị cần tìm với giá trị tại vị trí trung tâm để quyết định vùng dữ liệu (trước hay sau vị trí trung tâm) mà giá trị đó thuộc về.

Việc tìm kiếm sẽ cứ thế tiếp tục trong 1/2 tập hợp dữ liệu vừa xác định với cùng thủ tục, cho tới khi giá trị tại vị trí trung tâm là giá trị cần tìm hoặc khoảng tìm kiếm tiến tới zero thì ngưng. Vì sau mỗi bước tìm kiếm miền dữ liệu lại giảm đi phân nữa, tuần tự tiến dần tới zero nên số lượng các bước tìm kiếm cũng tăng dần tới tối đa là log2(N). Vì vậy độ phức tạp của thuật toán này được xem là O(log2(N)). Mã nguồn C được trích từ VnSlib dưới đây, việc tìm kiếm được tiến hành trên dữ liệu đã được sắp xếp tăng dần.



Binh Nguyen - Bioz
Tìm kiếm nhị phân (Binary search) Reviewed by Bioz on 2:10:00 PM Rating: 5
All Rights Reserved by IEEV © 2009 - 2016
Powered By Blogger, Designed by Sweetheme

Contact Form

Name

Email *

Message *

Powered by Blogger.