Wikipedia

Khác biệt giữa bản sửa đổi của “Tìm kiếm nhị phân”

Duyệt lịch sử tương tác
← Thay đổi trướcThay đổi sau →
Nội dung được xóa Nội dung được thêm vào
Trực quanMã wiki
Không có tóm lược sửa đổi
Không có tóm lược sửa đổi
Dòng 1:
{{đang dịch|Binary search algorithm|en}}▼
{{Infobox algorithm
|class=[[Thuật toán tìm kiếm]]
Hàng 12 ⟶ 13:
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#LogarithmicThời timegian logarit|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.
Hàng 127 ⟶ 128:
 
==Hiệu suất==
▲{{đang dịch|Binary search algorithm|en}}
[[File:Binary search example tree.svg|thumb|upright=0.75|Một [[Cây (cấu trúc dữ liệu)|cây]] biểu diễn tìm kiếm nhị phân. Mảng được dùng trong ví dụ này là <math>[20, 30, 40, 50, 80, 90, 100]</math> và giá trị cần tìm là <math>40</math>.]]
[[File:Binary search complexity.svg|thumb|upright=2|Trường hợp tệ nhất là khi quá trình tìm kiếm phải đi tới bậc sâu nhất của cây, còn trường hợp tốt nhất là khi giá trị cần tìm chính là phần tử đứng giữa.]]
Dòng 151:
==== Tìm kiếm thành công ====
<!-- E stands for "expected" -->
InKhi thebiểu binarydiễn treebằng representationcây nhị phân, amột successfullầm searchtìm cankiếm bethành representedcông bycó athể pathđược frombiểu thediễn rootbằng tomột theđường targetđi nodetừ gốc tới nút cần tìm, calledgọi anlà ''đường trong'' (''internal path''). TheĐộ lengthdài ofcủa amột pathđường islà the number ofsố edges (connections between nodes) thatmà theđường pathđó passesđi throughqua. TheSố phép lặp numbermà ofmột iterationslần performedtìm bykiếm athực searchhiện, givenvới thatđiều thekiện correspondingđộ pathdài hascủa lengthđường tương ứng với lần tìm đó là <math>l</math>, islà <math>l + 1</math> countingtính cả phép thelặp initialban iterationđầu. The''Độ dài đường trong'' (''internal path length'') islà thetổng sumđộ ofdài thetất lengthscả ofcác allđường unique internal pathstrong. SinceDo therechỉ iscó onlymột oneđường pathduy fromnhất thetừ rootgốc totới anybất singlecứ nodenút nào, eachmỗi internalđường pathtrong representsđó abiểu searchdiễn forcho amột specificphép elementtìm kiếm phần tử tương ứng. IfNếu there arecó <math>n</math> elements, which is aphần positive integertử, andvà theđộ internaldài pathđường lengthtrong islà <math>I(n)</math>, thenthì thesố averagephép numberlặp oftrung iterationsbình forcho amột successfullần searchtìm kiếm thành công là <math>T(n) = 1 + \frac{I(n)}{n}</math>, withtrong theđó oneđã iterationcộng addedthêm tomột countbước thelặp initialở iterationđầu.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsectionphân mục "Further analysis of binary search"}}
 
Since binary search is the optimal algorithm for searching with comparisons, this problem is reduced to calculating the minimum internal path length of all binary trees with <math>n</math> nodes, which is equal to:{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}}
Dòng 220:
Ngay cả trường hợp phép so sánh có nhiễu, có những thuật toán mở rộng để giải quyết cùng bài toán như thuật toán tìm kiếm nhị phân.<ref>{{chú thích|last1 = Karp|first1= Richard M.| last2=Kleinberg|first2= Robert|title = Noisy binary search and its applications|booktitle = Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms|series = SODA '07|year = 2007| isbn = 978-0-898716-24-5| location = New Orleans, Louisiana|pages = 881--890|numpages = 10|url = http://portal.acm.org/citation.cfm?id=1283383.1283478|acmid = 1283478|publisher = Society for Industrial and Applied Mathematics|address = Philadelphia, PA, USA}}</ref>
 
==Ghi chú và tham khảo==
<!-- Referencing conventions for this article: use CS1 templates, add book and monograph sources to the Works section and then cite them using Harvard citations, directly cite other sources. Source titles are in sentence case, but the first letter of proper nouns (e.g., "Bayesian") is capitalized. -->
{{Tham khảo}}
 
=== Ghi chú ===
{{Notelist}}
 
=== Chú thích ===
{{Reflist|30em}}
 
=== Tài liệu ===
{{columns-list|colwidth=30em|style=font-size:90%;|
<!-- * {{cite book|last1=Alexandrescu|first1=Andrei|title=The D Programming Language|date=2010|publisher=Addison-Wesley Professional|location=Upper Saddle River, New Jersey|isbn=0-321-63536-1|ref=harv}}-->
* {{cite book
| last = Bentley
| first = Jon
| authorlink = Jon Bentley (nhà khoa học máy tính)
| title = Programming pearls
| edition = 2nd
| publisher = [[Addison-Wesley]]
| year = 2000
| isbn = 978-0-201-65788-3|ref=harv}}
* {{cite book|last1=Butterfield|first1=Andrew|last2=Ngondi|first2=Gerard E.|title=A dictionary of computer science|date=2016|publisher=[[Oxford University Press]]|location=Oxford, UK|isbn=978-0-19-968897-5|edition=7th|ref=harv}}
* {{cite book | title=Data structures and algorithms | publisher=[[World Scientific]] | last1=Chang|first1=Shi-Kuo| year=2003 | location=Singapore | isbn=978-981-238-348-8 | volume=13 | work=Software Engineering and Knowledge Engineering|ref=harv}}
* {{cite book
| last1 = Cormen
| first1 = Thomas H.
| author1-link=Thomas H. Cormen
| last2= Leiserson
| first2= Charles E.
| author2-link=Charles E. Leiserson
| last3= Rivest
| first3= Ronald L.
| author3-link=Ron Rivest
| last4= Stein
| first4=Clifford
| author4-link=Clifford Stein
|title=Introduction to algorithms
| year = 2009
| edition = 3rd
| publisher = MIT Press and McGraw-Hill
| isbn = 978-0-262-03384-8
| ref = harv
| title-link = Introduction to Algorithms
}}
* {{cite book|last1=Fitzgerald|first1=Michael|title=Ruby pocket reference|date=2007|publisher=[[O'Reilly Media]]|location=Sebastopol, California|isbn=978-1-4919-2601-7|ref=harv}}
* {{cite book|last1=Goldman|first1=Sally A.|last2=Goldman|first2=Kenneth J.|title=A practical guide to data structures and algorithms using Java|date=2008|publisher=[[CRC Press]]|location=Boca Raton, Florida|isbn=978-1-58488-455-2|ref=harv}}
* {{cite book |last1=Kasahara |first1=Masahiro |last2=Morishita |first2=Shinichi |title=Large-scale genome sequence processing |date=2006 |publisher=Imperial College Press |location=London, UK |isbn=978-1-86094-635-6 |ref=harv}}
* {{cite book|last=Knuth|first=Donald|year=1997|authorlink=Donald Knuth|title=Fundamental algorithms|series=[[The Art of Computer Programming]]|volume=1|edition=3rd|location=Reading, MA|publisher=Addison-Wesley Professional|ref=harv|isbn=978-0-201-89683-1}}
* {{cite book|last=Knuth|first=Donald|year=1998|authorlink=Donald Knuth|title=Sorting and searching|series=[[The Art of Computer Programming]]|volume=3|edition=2nd|location=Reading, MA|publisher=Addison-Wesley Professional|ref=harv|isbn=978-0-201-89685-5}}
* {{cite book|last=Knuth|first=Donald|year=2011|authorlink=Donald Knuth|title=Combinatorial algorithms|series=[[The Art of Computer Programming]]|volume=4A|edition=1st|location=Reading, MA|publisher=Addison-Wesley Professional|ref=harv|isbn=978-0-201-03804-0}}
<!-- * {{cite book|last1=Leiss|first1=Ernst|title=A Programmer's Companion to Algorithm Analysis|date=2007|publisher=CRC Press|location=Boca Raton, Florida|isbn=1-58488-673-0|ref=harv}} -->
* {{cite book|last1=Moffat|first1=Alistair|last2=Turpin|first2=Andrew|title=Compression and coding algorithms|date=2002|publisher=Kluwer Academic Publishers|location=Hamburg, Germany|isbn=978-0-7923-7668-2|ref=harv|doi=10.1007/978-1-4615-0935-6}}
* {{cite book|last1=Sedgewick|first1=Robert|last2=Wayne|first2=Kevin|authorlink1=Robert Sedgewick (computer scientist)|title=Algorithms|date=2011|publisher=Addison-Wesley Professional|location=Upper Saddle River, New Jersey|isbn=978-0-321-57351-3|edition=4th|ref=harv|url=http://algs4.cs.princeton.edu/home/}} Condensed web version {{open access}}; book version {{closed access}}.
* {{cite book|last1=Stroustrup|first1=Bjarne|authorlink=Bjarne Stroustrup|title=The C++ programming language|edition=4th|date=2013|publisher=Addison-Wesley Professional|location=Upper Saddle River, New Jersey|isbn=978-0-321-56384-2|ref=harv}}
}}
 
[[Thể loại:Giải thuật tìm kiếm]]
Lấy từ “https://vi.wikipedia.org/wiki/Tìm_kiếm_nhị_phân”