Wikipedia:Today's featured article/October 29, 2018: Difference between revisions
update recently featured list |
Art LaPella (talk | contribs) m uncapitalize |
||
| Line 1: | Line 1: | ||
{{TFAIMAGE|Binary search tree search 4.svg|A |
{{TFAIMAGE|Binary search tree search 4.svg|A binary search tree }} |
||
A '''[[binary search algorithm]]''' is a method to determine the position of a target value within a [[sorted array]] (an ordered list). Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and so on. If the remaining half at any stage is found to be empty, then the target is not in the array. Even though the idea is simple, implementing binary search correctly requires attention to some subtleties about its exit conditions and midpoint calculation. Binary search runs in [[Time complexity#Logarithmic time|logarithmic time]] in the [[Best, worst and average case|worst case]]. It is faster than [[linear search]] except for small arrays, but the array must be sorted first. Although specialized [[data structures]] designed for fast searching, such as [[hash tables]], can be searched more efficiently, binary search applies to a wider range of problems. {{TFAFULL|Binary search algorithm}} |
A '''[[binary search algorithm]]''' is a method to determine the position of a target value within a [[sorted array]] (an ordered list). Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and so on. If the remaining half at any stage is found to be empty, then the target is not in the array. Even though the idea is simple, implementing binary search correctly requires attention to some subtleties about its exit conditions and midpoint calculation. Binary search runs in [[Time complexity#Logarithmic time|logarithmic time]] in the [[Best, worst and average case|worst case]]. It is faster than [[linear search]] except for small arrays, but the array must be sorted first. Although specialized [[data structures]] designed for fast searching, such as [[hash tables]], can be searched more efficiently, binary search applies to a wider range of problems. {{TFAFULL|Binary search algorithm}} |
||
Latest revision as of 04:29, 22 October 2018
A binary search algorithm is a method to determine the position of a target value within a sorted array (an ordered list). Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and so on. If the remaining half at any stage is found to be empty, then the target is not in the array. Even though the idea is simple, implementing binary search correctly requires attention to some subtleties about its exit conditions and midpoint calculation. Binary search runs in logarithmic time in the worst case. It is faster than linear search except for small arrays, but the array must be sorted first. Although specialized data structures designed for fast searching, such as hash tables, can be searched more efficiently, binary search applies to a wider range of problems. (Full article...)