Introduction to Search Algorithms
A search algorithm is an algorithm that evaluates a number of possible solutions to a given problem and returns the best one.
Linear Search Algorithm
A linear search algorithm,also called Sequential Search, is checking every value of a data list, one at a time, in sequence until a match is found.
Let’s take for example, an algorithm that searches through an array of numbers and compares every value within it with a given “match” number.
C++ Implementation
#include<iostream>
using namespace std;
int linearSearch(int v[], int n, int value){
for(int i = 0; i < n; i++)
if(v[i] == value)
return 1;
return -1;
}
int main(){
int v[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
cout << linearSearch(v, 9, 4) << endl;
}
It’s preety straight-forward.We have the “num” array made up of 10 elements and we check each of them in the for-loop to see if they match our given number(“match”).
A linear search algorithm has a complexity of O(n).
Binary Search Algorithm
A binary search algorithm is an algorithm used for finding a specific value in a sorted list.
The implementation is simple:
First we get the middle element of the array.If the middle element is equal with the value to be found, the algorithm stops.If not, we have the following :
- If the value to be found is less than the middle element, then perform the above operations for the part before the middle element (or the left side).
- If the value to be found is greater than the middle element, then perform the above operations for the part after the middle element (of the right side).
Here’s an example to help you understand better:
Let’s say we have the following array : { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } and we want find number 7.
First the middle it’s taken, that means 5, and compared with our given number, 7.Obviously 7 > 5, so now the array looks like this : { 6, 7, 8, 9, 10 }. Now 7 < 8 and the next part looks like this : { 6, 7 }. 7 == 7 => Element found.
C++ Iterative Implementation
#include<iostream>
using namespace std;
int binarySearch(int v[], int n, int value){
int low = 0, high = n, mid;
while(low < high)
{
mid = low + (high - low) / 2;
if(v[mid] == value)
return 1;
else if(v[mid] < value)
low = mid + 1;
else
high = mid - 1;
}
if(low < n && v[low] == value)
return 1;
else
return -1;
}
int main(){
int v[] = { 1, 2 , 3, 4 , 5 , 6 ,7 , 8, 9 , 10 };
cout << binarySearch(v, 10, 5) << endl;
}
And the C++ Recursive Implementation also :
#include<iostream>
using namespace std;
int binarySearchRec(int v[], int value, int low, int high){
if(high < low)
return -1;
int mid = low + ((high - low) / 2);
if(v[mid] > value)
return binarySearchRec(v, value, low, mid-1);
else if(v[mid] < value)
return binarySearchRec(v, value, mid+1, high);
else
return 1;
}
int main(){
int v[] = { 1, 2 , 3, 4 , 5 , 6 ,7 , 8, 9 , 10 };
cout << binarySearchRec(v, 2, 0, 9);
}
The recursive version does the same thing: it searches for the given value.If it doesn’t find it, it call itself performing the exact same process explained above.The difference, I suppose you got it already, is the absence of loops; the function calls itself with the parameters specified by case.
Tip : The iterative version is usually much faster and uses less memory.
Hope this was helpful and easy to understand.We’ll be back with more search algorithms soon.