Can anyone solve or narrow down the answer to Binary Algorithms

Open main menu

Wikipedia

Binary search algorithm

Article Talk

Language

Watch

Edit

This article is about searching a finite sorted array. For searching continuous function values, see bisection method.

In computer science, binary search, also known as half-interval search,[1] logarithmic search,[2] or binary chop,[3] is a search algorithm that finds the position of a target value within a sorted array.[4][5] 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 repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

Binary search algorithm

Binary Search Depiction.svg

Visualization of the binary search algorithm where 7 is the target value

Class

Search algorithm

Data structure

Array

Worst-case performance

O(log n)

Best-case performance

O(1)

Average performance

O(log n)

Worst-case space complexity

O(1)

Binary search runs in logarithmic time in the worst case, making O ( log ⁡ n ) {\displaystyle O(\log n)} O(\log n) comparisons, where n {\displaystyle n} n is the number of elements in the array.[a][6] Binary search is faster than linear search except for small arrays. However, the array must be sorted first to be able to apply binary search. There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search. However, binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.

There are numerous variations of binary search. In particular, fractional cascading speeds up binary searches for the same value in multiple arrays. Fractional cascading efficiently solves a number of search problems in computational geometry and in numerous other fields. Exponential search extends binary search to unbounded lists. The binary search tree and B-tree data structures are based on binary search.

AlgorithmEdit

Binary search works on sorted arrays. Binary search begins by comparing an element in the middle of the array with the target value. If the target value matches the element, its position in the array is returned. If the target value is less than the element, the search continues in the lower half of the array. If the target value is greater than the element, the search continues in the upper half of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration.[7]

ProcedureEdit

Given an array A {\displaystyle A} A of n {\displaystyle n} n elements with values or records A 0 , A 1 , A 2 , … , A n − 1 {\displaystyle A_{0},A_{1},A_{2},\ldots ,A_{n-1}} {\displaystyle A_{0},A_{1},A_{2},\ldots ,A_{n-1}}sorted such that A 0 ≤ A 1 ≤ A 2 ≤ ⋯ ≤ A n − 1 {\displaystyle A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}} {\displaystyle A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}}, and target value T {\displaystyle T} T, the following subroutine uses binary search to find the index of T {\displaystyle T} T in A {\displaystyle A} A.[7]

Set L {\displaystyle L} L to 0 {\displaystyle 0} 0 and R {\displaystyle R} R to n − 1 {\displaystyle n-1} n-1.

If L > R {\displaystyle L>R} {\displaystyle L>R}, the search terminates as unsuccessful.

Set m {\displaystyle m} m (the position of the middle element) to the floor of L + R 2 {\displaystyle {\frac {L+R}{2}}} {\displaystyle {\frac {L+R}{2}}}, which is the greatest integer less than or equal to L + R 2 {\displaystyle {\frac {L+R}{2}}} {\displaystyle {\frac {L+R}{2}}}.

If A m < T {\displaystyle A_{m}<T} {\displaystyle A_{m}<T}, set L {\displaystyle L} L to m + 1 {\displaystyle m+1} m+1 and go to step 2.

If A m > T {\displaystyle A_{m}>T} {\displaystyle A_{m}>T}, set R {\displaystyle R} R to m − 1 {\displaystyle m-1} m-1 and go to step 2.

Now A m = T {\displaystyle A_{m}=T} {\displaystyle A_{m}=T}, the search is done; return m {\displaystyle m} m.

This iterative procedure keeps track of the search boundaries with the two variables L {\displaystyle L} L and R {\displaystyle R} R. The procedure may be expressed in pseudocode as follows, where the variable names and types remain the same as above, floor is the floor function, and unsuccessful refers to a specific value that conveys the failure of the search.[7]

binary-search

function binary_search(A, n, T) is

L := 0

R := n − 1

while L ≤ R do

m := floor((L + R) / 2)

if A[m] < T then

L := m + 1

else if A[m] > T then

R := m − 1

else:

return m

return unsuccessful

Alternatively, the algorithm may take the ceiling of L + R 2 {\displaystyle {\frac {L+R}{2}}} {\displaystyle {\frac {L+R}{2}}}. This may change the result if the target value appears more than once in the array.

Alternative procedureEdit

In the above procedure, the algorithm checks whether the middle element ( m {\displaystyle m} m) is equal to the target ( T {\displaystyle T} T) in every iteration. Some implementations leave out this check during each iteration. The algorithm would perform this check only when one element is left (when L = R {\displaystyle L=R} {\displaystyle L=R}). This results in a faster comparison loop, as one comparison is eliminated per iteration, while it requires only one more iteration on average.[8]

Hermann Bottenbruch published the first implementation to leave out this check in 1962.[8][9]

Set L {\displaystyle L} L to 0 {\displaystyle 0} 0 and R {\displaystyle R} R to n − 1 {\displaystyle n-1} n-1.

While L ≠ R {\displaystyle L\neq R} {\displaystyle L\neq R},

Set m {\displaystyle m} m (the position of the middle element) to the ceiling of L + R 2 {\displaystyle {\frac {L+R}{2}}} {\displaystyle {\frac {L+R}{2}}}, which is the least integer greater than or equal to L + R 2 {\displaystyle {\frac {L+R}{2}}} {\displaystyle {\frac {L+R}{2}}}.

If A m > T {\displaystyle A_{m}>T} {\displaystyle A_{m}>T}, set R {\displaystyle R} R to m − 1 {\displaystyle m-1} m-1.

Else, A m ≤ T {\displaystyle A_{m}\leq T} ; set L {\displaystyle L} to m {\displaystyle m} .

Now L = R {\displaystyle L=R} , the search is done. If A L = T {\displaystyle A_{L}=T} , return L {\displaystyle L} . Otherwise, the search terminates as unsuccessful.

Where ceil is the ceiling function, the pseudocode for this version is:

function binary_search_alternative(A, n, T) is

L := 0

R := n − 1

while L != R do

m := ceil((L + R) / 2)

if A[m] > T then

R := m − 1

else:

L := m

if A[L] = T then

return L

return unsuccessful

Duplicate elementsEdit

The procedure may return any index whose element is equal to the target value, even if there are duplicate elements in the array. For example, if the array to be searched was [ 1 , 2 , 3 , 4 , 4 , 5 , 6 , 7 ] {\displaystyle [1,2,3,4,4,5,6,7]} and the target was 4 {\displaystyle 4} , then it would be correct for the algorithm to either return the 4th (index 3) or 5th (index 4) element. The regular procedure would return the 4th element (index 3) in this case. It does not always return the first duplicate (consider [ 1 , 2 , 4 , 4 , 4 , 5 , 6 , 7 ] {\displaystyle [1,2,4,4,4,5,6,7]} which still returns the 4th element). However, it is sometimes necessary to find the leftmost element or the rightmost element for a target value that is duplicated in the array. In the above example, the 4th element is the leftmost element of the value 4, while the 5th element is the rightmost element of the value 4. The alternative procedure above will always return the index of the rightmost element if such an element exists.[9]

Procedure for finding the leftmost elementEdit

To find the leftmost element, the following procedure can be used:[10]

Set L {\displaystyle L} to 0 {\displaystyle 0} and R {\displaystyle R} to n {\displaystyle n} .

While L < R {\displaystyle L<R} ,

Set m {\displaystyle m} (the position of the middle element) to the floor of L + R 2 {\displaystyle {\frac {L+R}{2}}} , which is the greatest integer less than or equal to L + R 2 {\displaystyle {\frac {L+R}{2}}} .

If A m < T {\displaystyle A_{m}<T} , set L {\displaystyle L} to m + 1 {\displaystyle m+1} .

Else, A m ≥ T {\displaystyle A_{m}\geq T} ; set R {\displaystyle R} to m {\displaystyle m} .

Return L {\displaystyle L} .

If L < n {\displaystyle L<n} and A L = T {\displaystyle A_{L}=T} , then A L {\displaystyle A_{L}} is the leftmost element that equals T {\displaystyle T} . Even if T {\displaystyle T} is not in the array, L {\displaystyle L} is the rank of T {\displaystyle T} in the array, or the number of elements in the array that are less than T {\displaystyle T} .

Where floor is the floor function, the pseudocode for this version is:

function binary_search_leftmost(A, n, T):

L := 0

R := n

while L < R:

m := floor((L + R) / 2)

if A[m] < T:

L := m + 1

else:

R := m

return L

Procedure for finding the rightmost elementEdit

To find the rightmost element, the following procedure can be used:[10]

Set L {\displaystyle L} to 0 {\displaystyle 0} and R {\displaystyle R} to n {\displaystyle n} .

While L < R {\displaystyle L<R} ,

Set m {\displaystyle m} (the position of the middle element) to the floor of L + R 2 {\displaystyle {\frac {L+R}{2}}} , which is the greatest integer less than or equal to L + R 2 {\displaystyle {\frac {L+R}{2}}} .

If A m > T {\displaystyle A_{m}>T} , set R {\displaystyle R} to m {\displaystyle m} .

Else, A m ≤ T {\displaystyle A_{m}\leq T} ; set L {\displaystyle L} to m + 1 {\displaystyle m+1} .

Return R − 1 {\displaystyle R-1} .

If R > 0 {\displaystyle R>0} and A R − 1 = T {\displaystyle A_{R-1}=T} , then A R − 1 {\displaystyle A_{R-1}} is the rightmost element that equals T {\displaystyle T} . Even if T {\displaystyle T} is not in the array, n − R {\displaystyle n-R} is the number of elements in the array that are greater than T {\displaystyle T} .

Where floor is the floor function, the pseudocode for this version is:

function binary_search_rightmost(A, n, T):

L := 0

R := n

while L < R:

m := floor((L + R) / 2)

if A[m] > T:

R := m

else:

L := m + 1

return R - 1

Approximate matchesEdit

Binary search can be adapted to compute approximate matches. In the example above, the rank, predecessor, successor, and nearest neighbor are shown for the target value 5 {\displaystyle 5} , which is not in the array.

The above procedure only performs exact matches, finding the position of a target value. However, it is trivial to extend binary search to perform approximate matches because binary search operates on sorted arrays. For example, binary search can be used to compute, for a given value, its rank (the number of smaller elements), predecessor (next-smallest element), successor (next-largest element), and nearest neighbor. Range queries seeking the number of elements between two values can be performed with two rank queries.[11]

Rank queries can be performed with the procedure for finding the leftmost element. The number of elements less than the target value is returned by the procedure.[11]

Predecessor queries can be performed with rank queries. If the rank of the target value is r {\displaystyle r} , its predecessor is r − 1 {\displaystyle r-1} .[12]

For successor queries, the procedure for finding the rightmost element can be used. If the result of running the procedure for the target value is r {\displaystyle r} , then the successor of the target value is r + 1 {\displaystyle r+1} .[12]

The nearest neighbor of the target value is either its predecessor or successor, whichever is closer.

Range queries are also straightforward.[12] Once the ranks of the two values are known, the number of elements greater than or equal to the first value and less than the second is the difference of the two ranks. This count can be adjusted up or down by one according to whether the endpoints of the range should be considered to be part of the range and whether the array contains entries matching those endpoints.[13]

Performance

Binary search versus other schemes

Variations

History

Implementation issues

Library support

See also

Notes and references

External links

Last edited 14 days ago by Ramapitecus

Wikipedia

Content is available under CC BY-SA 3.0 unless otherwise noted.

Privacy policy

Terms of Use

Desktop