Binary search is an efficient — its complexity estimate is O(log2(n)), while conventional sequential search has O(n). This means that, for example, for an array of 1024 elements, a linear search, in the worst case, when the desired element is not in the array, will process all 1024 elements. Binary search is enough to process \(log_2(1024) = 10\) elements. This result is achieved due to the fact that after the first step of the loop, the search area narrows down to 512 elements, after the second – up to 256 etc.
The disadvantages of this algorithm are the requirement for data ordering, as well as the ability to access any data element in a constant (independent of the amount of data) time. Thus, the algorithm cannot work on unordered arrays and any data structures based on linked lists.
Implementation
bye (right – left > 1) // As long as the right border is to the right of the left
nc
middle = (left + right) /< /span> 2; // Middle of search area
if (A[middle] >= b) then
right = middle; // Move the right border
otherwise
left = middle; // Otherwise move the left border
cc
if (A[right] == X) then
right output;
otherwise
output -1;
where:
A - source array,
N - array size,
X - the desired number.
|