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

=== DerivationTrường ofhợp averagetrung casebình ===

Số phép lặp trung bình được thực hiện bởi thuật toán tùy thuộc vào xác suất mỗi phần tử được thực hiện tìm kiếm. Trường hợp trung bình khi tìm kiếm thành công và không thành công là khác nhau. TheTa averagegiả numbersử ofmỗi iterationsphần performedtử bycó binaryxác searchsuất dependsđược ontìm thenhư probabilitynhau ofnếu eachtìm elementkiếm beingthành searchedcông. TheNếu averagetìm casekiếm iskhông differentthành for successful searches and unsuccessful searches. It will be assumed that each element is equally likely to be searched for successful searches. For unsuccessful searchescông, itta willgiả besử assumed that thecác [[IntervalKhoảng (mathematicstoán học)|intervalskhoảng]] betweengiữa và ngoài các andphần outsidetử elementscó arexác equallysuất likelyđược totìm begiống searchednhau. Trường hợp trung bình khi tìm kiếm thành công là số phép lặp cần thực hiện để tìm mọi phần tử chính xác một lần, chia cho <math>n</math>, số phần tử trong mảng. Trường hợp trung bình khi tìm kiếm không thành công là số phép lặp cần thực hiện để tìm một phần tử trong mọi khoảng chính xác một lần, chia cho <math>n + 1</math> khoảng.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Further analysis of binary search"}}

Khi biểu diễn bằng cây nhị phân, một lần tìm kiếm thành công có thể được biểu diễn bằng một đường đi từ gốc tới nút cần tìm, gọi là ''đường trong'' (''internal path''). Độ dài của một đường là số edges (connectionsđường betweennối nodesgiữa các nút) mà đường đó đi qua. Số phép lặp mà một lần tìm kiếm thực hiện, với điều kiện độ dài của đường tương ứng với lần tìm đó là <math>l</math>, là <math>l + 1</math> tính cả phép lặp ban đầu. ''Độ dài đường trong'' (''internal path length'') là tổng độ dài tất cả các đường trong. Do chỉ có một đường duy nhất từ gốc tới bất cứ nút nào, mỗi đường trong đó biểu diễn cho một phép tìm kiếm phần tử tương ứng. Nếu có <math>n</math> phần tử, và độ dài đường trong là <math>I(n)</math>, thì số phép lặp trung bình cho một lần tìm kiếm thành công là <math>T(n) = 1 + \frac{I(n)}{n}</math>, trong đó đã cộng thêm một bước lặp ở đầu.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Further analysis of binary search"}}

UnsuccessfulTa searchescó canthể bebiểu representeddiễn bylần augmentingtìm thekiếm treekhông withthành công bằng cách thêm vào cây các ''externalnút nodesngoài'', whichtạo forms anthành ''extendedcây nhị phân binarymở treerộng''. Nếu một nút trong, hoặc một nút có trong cây, có ít hơn hai nút con, thì ta sẽ thêm vào các nút con bổ sung, gọi là các nút ngoài, để mỗi nút trong đều có hai nút con. By doing so, an unsuccessful search can be represented as a path to an external node, whose parent is the single element that remains during the last iteration. AnMột ''đường ngoài'' (''external path'') islà amột pathđường fromđi thetừ rootgốc tođến anmột externalnút nodengoài. The ''external path length'' is the sum of the lengths of all unique external paths. Nếu số phần tử là <math>n</math> (<math>n</math> là số nguyên dương), và độ dài đường ngoài là <math>E(n)</math>, thì số phép lặp trung bình cho một lần tìm kiếm không thành công là <math>T'(n)=\frac{E(n)}{n+1}</math>, trong đó đã tính một phép lặp lúc đầu. Trong công thức này, ta lấy độ dài đường ngoài chia cho <math>n+1</math> chứ không phải <math>n</math> vì có <math>n+1</math> đường ngoài biểu diễn cho các khoảng giữa và ngoài các phần tử trong mảng.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}

OnTrên mosthầu computerhết architectures,các thekiểu kiến trúc máy tính, [[CentralCPU|bộ processingvi unit|processorxử lý]] hascó abộ hardwarenhớ [[Cache (computingtin học)|cache]] separateriêng fromtách biệt khỏi [[Random-access memory|RAM]]. SinceDo theynằm arengay locatedtrong withinbộ thexử processor itselflý, cachesbộ arenhớ muchcache fastercó tothể accesstruy butcập usuallynhanh storehơn muchnhưng lessthường datachỉ thanchứa được ít dữ liệu hơn RAM. ThereforeDo đó, mosthầu processorshết storecác memorybộ locationsxử thatlý havelưu beenđịa accessedchỉ recently,những alongvùng withbộ memorynhớ locationsđã closeđược totruy itcập gần đây và cả những vùng bộ nhớ xung quanh chúng. ForVí exampledụ, whenkhi antruy arraycập elementvào ismột accessedphần tử trong mảng, thephần elementtử itselfnày, maycùng bevới storedcả alongnhững withphần thetử elementsđược thatlưu aregần storedđó, closecó tothể itđược inlưu vào trong RAM, makingđể itsau fasterđó tocó sequentiallythể accesstruy arraycập elementsnhanh thathơn aređược closevào incác indexphần totử eachkhác otherliền kề ([[tính địa phương trong truy xuất - ''locality of reference]]''). OnVới một mảng ađã sortedsắp arrayxếp, binaryquá searchtrình cantìm jumpkiếm tonhị distantphân memorycó locationsthể ifphải thenhảy arraysang iscác largevùng bộ nhớ nằm xa nếu mảng có kích thước lớn, unlikekhông algorithmsgiống (suchnhư ascác thuật toán (như [[lineartìm kiếm tuyến searchtính]] andhay [[lineardò probingtuyến tính]] introng [[hashbảng tablesbăm]]) whichtruy accesscập elementscác inphần sequencetử theo thứ tự lần lượt. ThisĐiều addsnày slightlylàm tothời thegian runningchạy timecủa ofthuật toán tăng lên đôi chút với các binarymảng searchlớn fortrên largehầu arrayshết oncác mosthệ systemsthống.<ref>{{cite journal|last1=Khuong|first1=Paul-Virak|last2=Morin|first2=Pat|author2-link= Pat Morin |title=Array Layouts for Comparison-Based Searching|journal=Journal of Experimental Algorithmics|volume=22|at=Article 1.3|doi=10.1145/289251.289255}}</ref>