Khác biệt giữa bản sửa đổi của “Tìm kiếm nhị phân”
Nội dung được xóa Nội dung được thêm vào
Không có tóm lược sửa đổi |
Không có tóm lược sửa đổi |
||
Dòng 16:
Có nhiều biến thể của phép tìm kiếm nhị phân. Cụ thể, phương pháp "đổ xuống một phần" (''fractional cascading'') giúp tăng tốc tìm kiếm nhị phân với cùng một giá trị trong nhiều mảng. Phương pháp này cho phép giải quyết hiệu quả một số vấn đề về tìm kiếm trong [[hình học tính toán]] và nhiều lĩnh vực khác. Thuật toán [[tìm kiếm mũ]] (''exponential search'') mở rộng tìm kiếm nhị phân sang các danh sách không có giới hạn. Các cấu trúc dữ liệu [[cây tìm kiếm nhị phân]] và [[B-cây]] được xây dựng dựa trên tìm kiếm nhị phân.
==
Thuật toán tìm kiếm nhị phân hoạt động trên các mảng đã được sắp xếp. Thuật toán bắt đầu bằng việc so sánh một phần tử đứng chính giữa mảng với giá trị cần tìm. Nếu bằng nhau, vị trí của nó trong mảng sẽ được trả về. Nếu giá trị cần tìm nhỏ hơn phần tử này, quá trình tìm kiếm tiếp tục ở nửa nhỏ hơn của mảng. Nếu giá trị cần tìm lớn hơn phần tử ở giữa, quá trình tìm kiếm tiếp tục ở nửa lớn hơn của mảng. Bằng cách này, ở mỗi phép lặp thuật toán có thể loại bỏ nửa mảng mà giá trị cần tìm chắc chắn không xuất hiện.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Algorithm B"}}
===Quy trình===
Cho một mảng <math>A</math> có <math>n</math> phần tử với các giá trị hoặc [[bản ghi]] <math>A_0,A_1,A_2,\ldots,A_{n-1}</math>đã được sắp xếp sao cho <math>A_0 \leq A_1 \leq A_2 \leq \cdots \leq A_{n-1}</math>, và giá trị cần tìm <math>T</math>, [[chương trình con]] sau đây sử dụng tìm kiếm nhị phân để tìm chỉ số của <math>T</math> trong <math>A</math>.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Algorithm B"}}
# Gán <math>L</math> với giá trị <math>0</math> và <math>R</math> với giá trị <math>n-1</math>.
# Nếu <math>L>R</math>, tìm kiếm kết thúc (không thành công).
# Gán <math>m</math> (vị trí của phần tử đứng giữa) với giá trị [[Phần nguyên|floor]] của <math>\frac{L+R}{2}</math>, tức là số nguyên lớn nhất nhỏ hơn hoặc bằng <math>\frac{L+R}{2}</math>.
# Nếu <math>A_m < T</math>, gán <math>L</math> với <math>m+1</math> và quay lại bước 2.
# Nếu <math>A_m > T</math>, gán <math>R</math> với <math>m-1</math> và quay lại bước 2.
# Khi <math>A_m = T</math>, quá trình tìm kiếm hoàn tất; trả về <math>m</math>.
Quy trình lặp này dùng hai biến <math>L</math> và <math>R</math> để lưu giới hạn tìm kiếm. Quy trình này có thể diễn giải bằng [[mã giả]] như dưới đây, trong đó tên các biến và kiểu giữ nguyên so với như trên, <code>floor</code> là hàm floor, và <code>không_thành_công</code> là một giá trị cụ thể thông báo tìm kiếm thất bại.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Algorithm B"}}
'''function''' binary_search(A, n, T) '''is'''
L := 0
R := n − 1
'''while''' L ≤ R '''do'''
m := floor((L + R) / 2)
'''if''' A[m] < T '''then'''
L := m + 1
'''else if''' A[m] > T '''then'''
R := m - 1
'''else''':
'''return''' m
'''return''' không_thành_công
Ngoài ra, thuật toán có thể lấy giá trị [[Phần nguyên|ceiling]] của <math>\frac{L+R}{2}</math>. Điều này có thể thay đổi kết quả nếu giá trị cần tìm xuất hiện nhiều hơn một lần trong mảng.
==== Cách làm khác ====
Trong quy trình trên, thuật toán kiểm tra phần tử ở giữa (<math>m</math>) có bằng giá trị cần tìm (<math>T</math>) không ở mỗi phép lặp. Một số cách làm bỏ qua bước này ở mỗi phép lặp. Khi đó thuật toán chỉ kiểm tra điều này khi chỉ còn một phần tử còn lại (khi <math>L=R</math>). Nhờ đó mà vòng lặp so sánh được thực hiện nhanh hơn do mỗi phép lặp đã loại bỏ được một bước so sánh. Tuy nhiên, với cách làm này thì số phép lặp trung bình tăng lên.<ref name="Bottenbruch1962">{{cite journal|last1=Bottenbruch|first1=Hermann|title=Structure and use of ALGOL 60|journal=[[Journal of the ACM]] |date=1 April 1962|volume=9|issue=2|pages=161–221 |issn=0004-5411|doi=10.1145/321119.321120 |ref=harv}} Procedure is described at p. 214 (§43), titled "Program for Binary Search".</ref>
[[Hermann Bottenbruch]] cho xuất bản cách áp dụng đầu tiên bỏ qua bước kiểm tra này vào năm 1962.<ref name="Bottenbruch1962" />{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "History and bibliography"}}
# Gán <math>L</math> với giá trị <math>0</math> và <math>R</math> với giá trị <math>n-1</math>.
# Khi <math>L \neq R</math>,
## Gán <math>m</math> (vị trí của phần tử đứng giữa) với giá trị [[Phần nguyên|ceiling]] của <math>\frac{L+R}{2}</math>, tức là số nguyên nhỏ nhất lớn hơn hoặc bằng <math>\frac{L+R}{2}</math>.
## Nếu <math>A_m > T</math>, gán <math>R</math> với <math>m-1</math>.
## Trường hợp còn lại, <math>A_m \leq T</math>; gán <math>L</math> với <math>m</math>.
# Khi <math>L=R</math>, quá trình tìm kiếm hoàn tất. Nếu <math>A_L=T</math>, trả về <math>L</math>. Nếu không, tìm kiếm thất bại.
Với <code>ceil</code> là hàm ceiling, mã giả cho phiên bản này như sau:
'''function''' binary_search_alternative(A, n, T) '''is'''
L := 0
R := n − 1
'''while''' L != R '''do'''
m := ceil((L + R) / 2)
'''if''' A[m] > T '''then'''
R := m - 1
'''else''':
L := m
'''if''' A[L] = T '''then'''
'''return''' L
'''return''' không_thành_công
=== Phần tử lặp lại ===
Quy trình trên có thể trả về bất cứ chỉ số nào có giá trị phần tử bằng giá trị cần tìm, kể cả khi trong mảng có các phần tử xuất hiện lặp lại. Ví dụ, với mảng <math>[1,2,3,4,4,5,6,7]</math> và giá trị cần tìm là <math>4</math>, thuật toán có thể trả về một trong hai kết quả đúng là phần tử thứ 4 (chỉ số là 3) hoặc thứ 5 (chỉ số là 4). Quy trình chuẩn trong trường hợp này sẽ trả về phần tử thứ 4 (chỉ số 3). Thuật toán này không phải lúc nào cũng trả về vị trí đầu tiên xuất hiện giá trị cần tìm (ví dụ với mảng <math>[1,2,4,4,4,5,6,7]</math>, kết quả trả về vẫn là phần tử thứ 4). Tuy nhiên, có một số trường hợp cần phải tìm phần tử nằm xa nhất về phía bên trái hoặc bên phải mang giá trị cần tìm khi giá trị này xuất hiện lặp lại trong mảng. Trong ví dụ trên, phần tử thứ 4 là phần tử đứng xa nhất về bên trái mang giá trị 4, trong khi phần tử thứ 5 là phần từ đứng xa nhất về bên phải mang giá trị 4. Cách làm thứ hai ở trên sẽ luôn trả về chỉ số của phần tử đứng xa nhất về bên phải nếu tồn tại các phần tử lặp lại.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "History and bibliography"}}
==== Quy trình tìm phần tử xa nhất về bên trái ====
Để tìm phần tử xa nhất về bên trái, ta có thể dùng quy trình sau:{{Sfn|Kasahara|Morishita|2006|pp=8–9}}
# Gán <math>L</math> với giá trị <math>0</math> và <math>R</math> với <math>n</math>.
# Khi <math>L < R</math>,
# Gán <math>m</math> (vị trí của phần tử đứng giữa) với giá trị [[Phần nguyên|floor]] của <math>\frac{L+R}{2}</math>, tức là số nguyên lớn nhất nhỏ hơn hoặc bằng <math>\frac{L+R}{2}</math>.
## Nếu <math>A_m < T</math>, gán <math>L</math> với <math>m+1</math>.
## Trường hợp còn lại, <math>A_m \geq T</math>; gán ''<math>R</math>'' với <math>m</math>.
# Trả về <math>L</math>.
Nếu <math>L < n</math> và <math>A_L = T</math> thì <math>A_L</math> là phần tử đứng xa nhất về bên trái có giá trị bằng <math>T</math>. Kể cả khi <math>T</math> không nằm trong mảng, <math>L</math> là [[#So khớp xấp xỉ|hạng]] của <math>T</math> trong mảng, hay số phần tử trong mảng nhỏ hơn <math>T</math>.
Với <code>floor</code> là hàm floor, mã giả cho phiên bản này như sau:
'''function''' binary_search_leftmost(A, n, T):
L := 0
R := n
'''while''' L < R:
m := floor((L + R) / 2)
'''if''' A[m] < T:
L := m + 1
'''else''':
R := m
'''return''' L
==== Quy trình tìm phần tử xa nhất về bên phải ====
Để tìm phần tử xa nhất về bên phải, ta có thể dùng quy trình sau:{{Sfn|Kasahara|Morishita|2006|pp=8–9}}
# Gán <math>L</math> với giá trị <math>0</math> và <math>R</math> với <math>n</math>.
# Khi <math>L < R</math>,
# Gán <math>m</math> (vị trí của phần tử đứng giữa) với giá trị [[Phần nguyên|floor]] của <math>\frac{L+R}{2}</math>, tức là số nguyên lớn nhất nhỏ hơn hoặc bằng <math>\frac{L+R}{2}</math>.
## Nếu <math>A_m > T</math>, gán <math>R</math> với <math>m</math>.
## Trường hợp còn lại, <math>A_m \leq T</math>; gán ''<math>L</math>'' với <math>m+1</math>.
# Trả về <math>R - 1</math>.
Nếu <math>L > 0</math> và <math>A_{L-1}=T</math>, thì <math>A_{L-1}</math> là phần tử đứng xa nhất về phía bên phải có giá trị bằng <math>T</math>. Kể cả khi ''<math>T</math>'' không có trong mảng, <math>n-L</math> sẽ là số phần tử trong mảng lớn hơn ''<math>T</math>''.
Với <code>floor</code> là hàm floor, mã giả cho phiên bản này như sau:
'''function''' binary_search_rightmost(A, n, T):
L := 0
R := n
'''while''' L < R:
m := floor((L + R) / 2)
'''if''' A[m] > T:
R := m
'''else''':
L := m + 1
'''return''' R - 1
== Thời gian thực thi ==
| |||