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
nKhông có tóm lược sửa đổi |
Không có tóm lược sửa đổi |
||
Dòng 10:
|optimal=Có
}}
Trong [[khoa học máy tính]], '''tìm kiếm nhị phân''' ({{lang-en|binary search}}), còn gọi là '''tìm kiếm nửa khoảng''' (''half-interval search''),<ref name="Williams1976">{{cite conference|last1=Williams, Jr.|first1=Louis F.|title=A modification to the half-interval search (binary search) method|conference=Proceedings of the 14th ACM Southeast Conference|date=22 April 1976|pages=95–101|doi=10.1145/503561.503582|url=https://dl.acm.org/citation.cfm?doid=503561.503582|publisher=ACM|accessdate=29 June 2018|archive-url=https://web.archive.org/web/20170312215255/http://dl.acm.org/citation.cfm?doid=503561.503582|archive-date=12 March 2017|url-status=live|df=dmy-all}}</ref> '''tìm kiếm logarit''' (''logarithmic search''),{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Binary search"}} hay '''binary chop''',{{Sfn|Butterfield|Ngondi|2016|p=46}} là một [[thuật toán tìm kiếm]] xác định vị trí của một giá trị cần tìm trong một mảng đã được sắp xếp.{{Sfn|Cormen|Leiserson|Rivest|Stein|2009|p=39}}<ref>{{MathWorld |title=Binary search |id=BinarySearch}}</ref> Thuật toán tiến hành so sánh giá trị cần tìm với phần tử đứng giữa mảng. Nếu hai giá trị không bằng nhau, phần nửa mảng không chứa giá trị cần tìm sẽ bị bỏ qua và tiếp tục tìm kiếm trên nửa còn lại, một lần nữa lấy phần tử ở giữa và so sánh với giá trị cần tìm, cứ thế lặp lại cho đến khi tìm thấy giá trị đó. Nếu phép tìm kiếm kết thúc khi nửa còn lại trống thì giá trị cần tìm không có trong mảng.
Tìm kiếm nhị phân chạy theo [[Độ phức tạp thời gian#Logarithmic time|thời gian cấp logarit]] trong [[Trường hợp tốt nhất, tệ nhất và trung bình|trường hợp tệ nhất]], thực hiện <math>O(\log n)</math> bước so sánh, trong đó <math>n</math> là số phần tử trong mảng, <math>O</math> là [[kí hiệu O lớn]], và <math>\log</math> là phép toán [[logarit]].<ref name="FloresMadpis1971">{{cite journal|last1=Flores|first1=Ivan|last2=Madpis|first2=George|title=Average binary search length for dense ordered lists|journal=[[Communications of the ACM]]|date=1 September 1971|volume=14|issue=9|pages=602–603|issn=0001-0782|doi=10.1145/362663.362752|bibcode=1985CACM...28...22S}}</ref> Thuật toán tìm kiếm nhị phân nhanh hơn so với [[tìm kiếm tuyến tính]], ngoại trừ các trường hợp mảng có kích thước nhỏ. Tuy nhiên, mảng phải được sắp xếp trước khi áp dụng tìm kiếm nhị phân. Một số [[cấu trúc dữ liệu]] chuyên dụng được thiết kế cho việc tìm kiếm nhanh, ví dụ như [[bảng băm]], có thể thực hiện tìm hiệu quả hơn tìm kiếm nhị phân. Tuy nhiên, thuật toán này có thể dùng để giải quyết nhiều loại vấn đề hơn, như tìm phần tử nhỏ nhất hoặc lớn nhất tiếp theo trong mảng so với giá trị cho trước, kể cả khi nó không có trong mảng.
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.
== Tổng quan ==
| |||