searching

Searching in programming :

         Searching is the most fundamental technique used in computer science.  It is the process of finding a particular item in the collection of items. Another use of searching algorithm is that it can check whether the particular item selected is present in the given collection of list or not. 

Searching techniques are of two types. They are linear search and binary search.

Linear Search:

 This is the most simplest and regular way to search a particular item. According to this algorithm the selected item will be checked with each and every element until the end. It checks each and every item in a sequence.

Code for linear search:

bool lineat_search(int a[], int length, int item)

{

  for(int i=0;i<length;i++)

  {

    if(item==a[i])

    {

      return true;

    }

  }

  return false;

}

Let's take an example. say a={1.9,2,4,6,3,7,5,8,0}... We need to find 3 in the given array. Now linear search starts from the beggining and checks whether the given number matches with the item or not.

Now let us consider the modified search where we need to return the position, where the item is found. To solve this modified search problem, we need to change two lines of the linearserch() function.

code:

 int linear_search(int a[],int length, int item)
{
   for(i=0;i<length;i++)
   {
     if(item==a[i])
     {
       return i;
     }
      return -1;
    }
}

Binary search:

  Binary search is a divide and conquer algorithm. According to binary search we need to divide the larger problems into smaller subproblems recursively until the problem is small enough that the solution is trival.

 for using this binary search algorithm the array should be sorted. If the array is sorted in the ascending order binary search starts with the middle element of the array. If the selected item matches to the middle element then it returns true. Otherwise if the item selected is less than the middle item it takes the upper half and checks with the middle element on the upper subpart. If that middle element matches to the selected item then it again returns true. Otherwise if the element is greater than the middle element then it cheks with the lower half of the system.

here is an algorithm for the binary search:

algorithm binary_search(A, left, right, item)

{

  if(left<=right)

  mid=left+right/2

 if(A[mid]==item)

 return true;

else if(item<A[mid])

        recurse on the left sub array

else if(item >a[mid])

        recurse on right sub array;

else 

  return false;

}