Thuật toán sắp xếp: BINARY SEARCH

Ý tưởng

Đối với những dãy số đã có thứ tự (tăng dần), các phần tử đã có quan hệ      ai-1 ≤ ai ≤ ai+1. Nếu x > ai thì x chỉ có thể xuất hiện trong đoạn [ai+1, aN], ngược lại nếu x < ai thì x chỉ có thể xuất hiện trong đoạn [a1, ai-1].

Giải thuật áp dụng nhận xét trên để giới hạn phạm vi tìm kiếm sau mỗi lần so sánh x với một phần tử trong dãy. Tại mỗi bước, so sánh x với phần tử nằm giữa dãy tìm kiếm hiện hành, dựa vào kết quả so sánh để quyết định giới hạn của dãy tìm kiếm ở bước kế tiếp là nửa trên hay nửa dưới của dãy hiện hành.

 

Giải thuật

           Bước 1left = 1;      right = N;       // tìm kiếm trên tất cả các phần tử

            Bước 2mid = (left + right)/2;      // lấy mốc so sánh

                        So sánh a[mid] với x

                        +   a[mid] = x: Tìm thấy. Dừng.

                        +   a[mid] > x: Tìm tiếp x trong dãy con aleft..amid-1

                                    right = mid – 1;

                        +   a[mid] < x: Tìm tiếp x trong dãy con amid+1..aright

                                    left = mid + 1;

            Bước 3:  Nếu leftright     Lặp lại bước 2.          // còn phần tử chưa xét                                   

                   Ngược lại: Dừng      

 

Chủ đề liên quan
Thuật toán sắp xếp: BINARY SEARCH

Cùng chuyên mục

Xem nhiều hôm nay