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 126:
'''return''' R - 1
==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.]]
Về mặt số phép so sánh, hiệu suất của thuật toán tìm kiếm nhị phân có thể được phân tích bằng cách biểu diễn quá trình chạy thuật toán trên cây nhị phân. Nút gốc của cây là phần tử đứng giữa mảng. Phần tử đứng giữa nửa nhỏ hơn là nút con bên trái của nút gốc, và phần tử đứng giữa nửa lớn hơn là nút con bên phải của nút gốc. Phần còn lại của cây cũng được dựng như vậy. Bắt đầu từ nút gốc, tùy theo giá trị cần tìm nhỏ hơn hay lớn hơn nút đang xét mà thuật toán sẽ duyệt theo cây con bên trái hay bên phải.<ref name="FloresMadpis1971" />{{sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Further analysis of binary search"}}
Trong trường hợp tệ nhất, thuật toán thực hiện <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> lần lặp so sánh, trong đó <math display="inline">\lfloor \rfloor</math> là ký hiệu của [[Phần nguyên|hàm floor]] cho kết quả là số nguyên lớn nhất nhỏ hơn hoặc bằng giá trị bên trong, và <math display="inline">\log_2</math> là phép [[Logarit|logarit nhị phân]]. Nguyên nhân là do khi gặp phải trường hợp tệ nhất, thuật toán phải đi tới bậc sâu nhất trong cây, và số bậc trong cây luôn bằng <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> với bất cứ phép tìm kiếm nhị phân nào.
Trường hợp tệ nhất còn có thể xảy ra khi giá trị cần tìm không có trong mảng. Nếu <math display="inline">n</math> ở dạng <math display="inline">2^\alpha - 1</math> thì trường hợp này luôn xảy ra. Nếu không, thuật toán có thể thực hiện <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math>phép lặp nếu phải đi tới bậc sâu nhất của cây. Tuy nhiên, nếu thuật toán kết thúc ngay ở bậc sâu thứ hai của cây, quá trình tìm kiếm có thể chỉ cần thực hiện <math display="inline">\lfloor \log_2 (n) \rfloor</math> phép lặp, ít hơn trường hợp tệ nhất một phép.{{sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), "Theorem B"}}
Giả sử mỗi phần tử có xác suất được thực hiện tìm kiếm như nhau, trung bình thuật toán tìm kiếm nhị phân thực hiện <math>\lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n</math> phép lặp khi phần tử cần tìm có mặt trong mảng, hay xấp xỉ bằng <math>\log_2(n) - 1</math>. Khi phần tử cần tìm không có trong mảng, thuật toán thực hiện trung bình <math>\lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1)</math> phép lặp, nếu giả sử khoảng giữa và bên ngoài các phần tử đều có xác suất được tìm như nhau.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), phân mục "Further analysis of binary search"}}
Trong trường hợp tốt nhất, khi giá trị cần tìm nằm ngay giữa mảng, vị trí của nó được trả về ngay sau một phép lặp.{{Sfn|Chang|2003|p=169}}
In terms of iterations, không có thuật toán tìm kiếm nào chỉ bằng so sánh các phần tử có thể có hiệu suất trung bình hay thậm chí trong trường hợp tệ nhất tốt hơn tìm kiếm nhị phân. Cây so sánh biểu diễn tìm kiếm nhị phân có số bậc ít nhất có thể as every level above the lowest level of the tree is filled completely.{{Efn|Bất cứ thuật toán tìm kiếm nào chỉ dựa trên các phép so sánh có thể được biểu diễn bằng cây so sánh nhị phân. ''Đường trong'' (''internal path'') là bất kỳ đường nào đi từ gốc tới một nút có sẵn. Gọi <math>I</math> là ''độ dài đường trong'' (''internal path length''), hay tổng độ dài tất cả các đường trong của cây. Nếu mỗi phần tử có xác suất được tìm như nhau, trường hợp trung bình là <math>1 + \frac{I}{n}</math>, hoặc đơn giản hơn là một cộng với trung bình toàn bộ độ dài các đường trong trong cây. Nguyên nhân là do các đường trong biểu diễn các phần tử mà thuật toán tìm kiếm tiến hành so sánh với giá trị cần tìm. Độ dài của các đường này biểu diễn số phép lặp ''sau'' nút gốc. Làm phép cộng trung bình tổng độ dài các đường này với thêm một phép lặp nữa ở nút gốc sẽ ra trường hợp trung bình. Do đó, để giảm tối đa số phép so sánh trung bình, cần phải giảm độ dài đường trong <math>I</math>. Thực chất cây biểu diễn tìm kiếm nhị phân đã giảm tối đa độ dài đường trong. {{Harvnb|Knuth|1998}} chứng minh được rằng độ dài ''đường ngoài'' (''external path'' - the path length over all nodes where both children are present for each already-existing node) được giảm tối đa khi các nút ngoài (các nút không có nút con) nằm trong hai bậc liên tiếp của cây. Điều này cũng áp dụng với các đường trong do độ dài đường trong <math>I</math> có liên hệ tuyến tính với độ dài đường ngoài <math>E</math>. Với mỗi cây có <math>n</math> nút, <math>I = E - 2n</math>. Khi mỗi cây con có số nút bằng nhau, tương đương với khi mảng được chia thành hai nửa ở mỗi phép lặp, When each subtree has a similar number of nodes, or equivalently the array is divided into halves in each iteration, the external nodes as well as their interior parent nodes lie within two levels. It follows that binary search minimizes the number of average comparisons as its comparison tree has the lowest possible internal path length.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}}} Otherwise, the search algorithm can eliminate few elements in an iteration, increasing the number of iterations required in the average and worst case. This is the case for other search algorithms based on comparisons, as while they may work faster on some target values, the average performance over ''all'' elements is worse than binary search. By dividing the array in half, binary search ensures that the size of both subarrays are as similar as possible.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}
==== Độ phức tạp không gian ====
Thuật toán tìm kiếm nhị phân cần ba con trỏ để trỏ tới các phần tử, bất kể kích thước của mảng; đó có thể là chỉ số các phần tử trong mảng hoặc con trỏ tới địa chỉ trong bộ nhớ. Tuy nhiên, thuật toán cần ít nhất <math>\left \lceil \log_2(n) \right \rceil</math> bit để mã hóa một con trỏ tới một phần tử trong mảng có <math>n</math> phần tử.<ref>{{cite journal |author=Shannon, Claude E. |authorlink=Claude Shannon |title=A Mathematical Theory of Communication |journal=[[Bell System Technical Journal]] |volume=27 |issue=3 |pages=379–423 |date=July 1948 |doi=10.1002/j.1538-7305.1948.tb01338.x|hdl=11858/00-001M-0000-002C-4314-2 }}</ref> Do đó, độ phức tạp không gian của tìm kiếm nhị phân là <math>O(\log n)</math>. Ngoài ra, thuật toán còn cần <math>O(n)</math> không gian để lưu trữ mảng.
=== Derivation of average case ===
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. The average number of iterations performed by binary search depends on the probability of each element being searched. The average case is different for successful searches and unsuccessful searches. It will be assumed that each element is equally likely to be searched for successful searches. For unsuccessful searches, it will be assumed that the [[Interval (mathematics)|intervals]] between and outside elements are equally likely to be searched. 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"}}
==== Tìm kiếm thành công ====
<!-- E stands for "expected" -->
In the binary tree representation, a successful search can be represented by a path from the root to the target node, called an ''internal path''. The length of a path is the number of edges (connections between nodes) that the path passes through. The number of iterations performed by a search, given that the corresponding path has length <math>l</math>, is <math>l + 1</math> counting the initial iteration. The ''internal path length'' is the sum of the lengths of all unique internal paths. Since there is only one path from the root to any single node, each internal path represents a search for a specific element. If there are <math>n</math> elements, which is a positive integer, and the internal path length is <math>I(n)</math>, then the average number of iterations for a successful search <math>T(n) = 1 + \frac{I(n)}{n}</math>, with the one iteration added to count the initial iteration.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "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")}}
<math>
I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor
</math>
For example, in a 7-element array, the root requires one iteration, the two elements below the root require two iterations, and the four elements below require three iterations. In this case, the internal path length is:{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}}
<math>
\sum_{k=1}^7 \left \lfloor \log_2(k) \right \rfloor = 0 + 2(1) + 4(2) = 2 + 8 = 10
</math>
The average number of iterations would be <math>1 + \frac{10}{7} = 2 \frac{3}{7}</math> based on the equation for the average case. The sum for <math>I(n)</math> can be simplified to:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}
<math>
I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor = (n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2
</math>
Substituting the equation for <math>I(n)</math> into the equation for <math>T(n)</math>:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}
<math>
T(n) = 1 + \frac{(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2}{n} = \lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n
</math>
For integer <math>n</math>, this is equivalent to the equation for the average case on a successful search specified above.
==== Tìm kiếm không thành công ====
Unsuccessful searches can be represented by augmenting the tree with ''external nodes'', which forms an ''extended binary tree''. If an internal node, or a node present in the tree, has fewer than two child nodes, then additional child nodes, called external nodes, are added so that each internal node has two children. 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. An ''external path'' is a path from the root to an external node. The ''external path length'' is the sum of the lengths of all unique external paths. If there are <math>n</math> elements, which is a positive integer, and the external path length is <math>E(n)</math>, then the average number of iterations for an unsuccessful search <math>T'(n)=\frac{E(n)}{n+1}</math>, with the one iteration added to count the initial iteration. The external path length is divided by <math>n+1</math> instead of <math>n</math> because there are <math>n+1</math> external paths, representing the intervals between and outside the elements of the array.{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}
This problem can similarly be reduced to determining the minimum external path length of all binary trees with <math>n</math> nodes. For all binary trees, the external path length is equal to the internal path length plus <math>2n</math>.{{Sfn|Knuth|1997|loc=§2.3.4.5 ("Path length")}} Substituting the equation for <math>I(n)</math>:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}
<math>
E(n) = I(n) + 2n = \left[(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2\right] + 2n = (n + 1) (\lfloor \log_2 (n) \rfloor + 2) - 2^{\lfloor \log_2 (n) \rfloor + 1}
</math>
Substituting the equation for <math>E(n)</math> into the equation for <math>T'(n)</math>, the average case for unsuccessful searches can be determined:{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search"}}
<math>
T'(n) = \frac{(n + 1) (\lfloor \log_2 (n) \rfloor + 2) - 2^{\lfloor \log_2 (n) \rfloor + 1}}{(n+1)} = \lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1)
</math>
==== Performance of alternative procedure ====
Each iteration of the binary search procedure defined above makes one or two comparisons, checking if the middle element is equal to the target in each iteration. Assuming that each element is equally likely to be searched, each iteration makes 1.5 comparisons on average. A variation of the algorithm checks whether the middle element is equal to the target at the end of the search. On average, this eliminates half a comparison from each iteration. This slightly cuts the time taken per iteration on most computers. However, it guarantees that the search takes the maximum number of iterations, on average adding one iteration to the search. Because the comparison loop is performed only <math display="inline">\lfloor \log_2 (n) + 1 \rfloor</math> times in the worst case, the slight increase in efficiency per iteration does not compensate for the extra iteration for all but very large <math display="inline">n</math>.{{Efn|{{Harvnb|Knuth|1998}} showed on his [[MIX]] computer model, which Knuth designed as a representation of an ordinary computer, that the average running time of this variation for a successful search is <math display="inline">17.5 \log_2 n + 17</math> units of time compared to <math display="inline">18 \log_2 n - 16</math> units for regular binary search. The time complexity for this variation grows slightly more slowly, but at the cost of higher initial complexity. {{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Exercise 23"}}}}{{Sfn|Knuth|1998|loc=§6.2.1 ("Searching an ordered table"), subsection "Exercise 23"}}<ref>{{cite journal|last1=Rolfe|first1=Timothy J.|title=Analytic derivation of comparisons in binary search|journal=ACM SIGNUM Newsletter|date=1997|volume=32|issue=4|pages=15–19|doi=10.1145/289251.289255}}</ref>
=== Running time and cache use ===
In analyzing the performance of binary search, another consideration is the time required to compare two elements. For integers and strings, the time required increases linearly as the encoding length (usually the number of [[bit]]s) of the elements increase. For example, comparing a pair of 64-bit unsigned integers would require comparing up to double the bits as comparing a pair of 32-bit unsigned integers. The worst case is achieved when the integers are equal. This can be significant when the encoding lengths of the elements are large, such as with large integer types or long strings, which makes comparing elements expensive. Furthermore, comparing [[Floating-point arithmetic|floating-point]] values (the most common digital representation of [[real number]]s) is often more expensive than comparing integers or short strings.
On most computer architectures, the [[Central processing unit|processor]] has a hardware [[Cache (computing)|cache]] separate from [[Random-access memory|RAM]]. Since they are located within the processor itself, caches are much faster to access but usually store much less data than RAM. Therefore, most processors store memory locations that have been accessed recently, along with memory locations close to it. For example, when an array element is accessed, the element itself may be stored along with the elements that are stored close to it in RAM, making it faster to sequentially access array elements that are close in index to each other ([[locality of reference]]). On a sorted array, binary search can jump to distant memory locations if the array is large, unlike algorithms (such as [[linear search]] and [[linear probing]] in [[hash tables]]) which access elements in sequence. This adds slightly to the running time of binary search for large arrays on most systems.<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>
==Mở rộng==
| |||