Linear array search
Very often you need to find a given value in an array or report that it is not there. To do this, you need to look through all the elements of the array from the first to the last. As soon as an element equal to the given value X is found, the search should end and the result should be displayed. Such an algorithm is called linear.
A linear algorithm is used to find the maximum (minimum) element of an array. This is also a search algorithm. But here we are forced to go to the end of the array, because it is necessary to compare all elements with the current maximum (minimum) value and if the current element is greater (less) than the maximum (minimum) value, replace the maximum (minimum) value.
|
Another approach to solving this problem is possible. You can use an early exit from the loop if the required value is found.
In C++, the break statement is used to break out of a loop;
|
Binary Search
Binary (or binary) search is an efficient search algorithm and is faster than linear search. 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, but it is enough to process 10 elements with a binary search. 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 such an 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. Therefore, the algorithm cannot work on unordered arrays.
Algorithm
- Select middle element
A[c] and compare with X.
- If
X = A[c] then found (stop).
- If
X < A[c], search further in the first half.
- If
X > A[c], look further into the second half.
Implementation
L = 0; R=N; // initial segment
while ( L < R - 1)
{
c = (L + R) / 2; // found the middle
if ( X < A[c] ) // segment compression
R=c;
else
L = c;
}
if ( A[L] == X)
cout << "A" << L<< "]=" << x;
else
cout << "Not found";
where:
A - source array,
N - array size,
X - searched number,
Other implementations are possible.
For example, using an early exit from the loop
L = 0; R = N - 1;
while (R >= L)
{
c = (L + R) / 2;
if ( X == A[c] )
{
nX = c;
break;
}
if (X < A[c]) R = mid - 1;
if (X > A[c]) L = mid + 1;
}
if ( nX < 0)
cout << "Not found";
else
cout << "A" << nX<< "]=" << X;
|
Comparison of linear and binary search algorithms by the number of comparisons
Examples
| # |
Line Search |
Binary Search |
| 2 |
2 |
2 |
| 16 |
16 |
5 |
| 1024 |
1024 |
11 |
| 1048576 |
1048576 |
21 |
The advantage of binary sort is that it is faster.
Cons- a pre-sorted array is required.
|