Search Algorithms

Linear Search

It is the easiest search algorithm.The algorithm intends so check each and every element and stops when the required element is found.

Implementation

int getindex(int a[], int n, int target)
{
for(int i = 0; i < n ; i++)
if (a[i] == target) { return i; }
return -1;
}

void main()
{
int a[]={3,4,5,2,6,8,10};
int n=7; //no. of elements in the array
int index=getindex(a,n,6);
printf("index of 6 in array "a" is::%d",index);
}

explaination::The above code returns the index of element to be found...


Binary Search

Binary Search use Divide and rule algorithm to find the reqd. element in an already sorted list. The algorithm is deceptively simple. Pretend I was thinking of a number between 1 and 100. Every guess you take, I'll say higher or lower. The most efficient way to discover my number is to first guess 50. Higher. 75. Lower. 62. Higher 68. Yes!

Implementation

int findIndex(int a[],int n, int target) {
return binarySearch(a, target, 0, n);
};

int binarySearch(int a, int target,int start,int end) {
if (start > end) { return -1; } //does not exist

int middle = (start + end) / 2;
int value = a[middle];

if (value > target) { return binarySearch(a, target, start, middle-1); }
if (value < target) { return binarySearch(a, target, middle+1, end); }
return middle; //found!
}

int a[]={1, 4,6,8,9,12,32,45,56,58,78};
int n=11;
findIndex(a,n,12);