Thursday, May 10, 2012

What is linear search!!

Linear Search  is the one of the basic search algorithm used in computer science. This is also called brute force searching algorithm, because, it just starts the searching each element in the array from starting position until key found or end of the array. Here the advantage is with this algorithm  is that array of elements can be any order where as in binary search the elements should be in sorted order. This searching algorithm will be useful if the no. of elements in the array are less or small.

Algorithm for linear search:

1. Get the element key which needs to be search in the array
2. Get the array of the elements in which key needs to be search
3. take the elements from position zero  in the array
4. compare the element with key  matches stops the process
5. if not matches proceed for the next element until end of the array
6. repeat steps from 3 to 6

Time Complexity of Linear Search: The best case for this searching algorithm is O(1). Because , we may get the searchin key in the first position itself. And the worst case of linear search algorithm is O(n). Because we may get the searching key  in the last position in the array or we may not get the key  element in the array. Because of this complexity, its not advisable to use this searching algorithm if the no. of eleaments in the array more(probabley more than 100).
Program of linear search in C:
int linear_search(int arr[], int key, int max_pos)
{
    int pos;
    for(pos=0;pos<max_pos;pos++)
    {
        if(arr[pos]==key)
            return pos;
    }
    return -1;
}
main()
{
    int arr[10],i,pos,key;
    int startIndex=0;
    int endIndex=9;
    printf("enter the elements in array in sorted orderd only\n");
    for(i=0;i<10;i++)
    {
        scanf("%d",&arr[i]);
    }
    printf("enter the element to be searched\n");
    scanf("%d",&key);
    pos = linear_search(arr,key,endIndex);
    if(pos!=-1)
        printf("element %d find at position %d\n",key,pos);
    else
        printf("element not in the array\n");
}

Results:
enter the elements in array in sorted orderd only

234
45
56
78
90
12
23
123
534
765
enter the element to be searched
534
element 534 find at position 8



enter the elements in array in sorted orderd only
234
34
45
56
67
89
90
12
23
34
enter the element to be searched
1234
element not in the array

Tuesday, May 8, 2012

Binary Search !!

Binary Search  is used to find the given element in a sorted array of elements. This is one of the best searching algorithm. It follows the method devide and conquer. And the time complexity for this searching algorithm is O(log(n)) where n is no.of elements in the array. Binary search is very usefull if the no. of elements are more. The pre-condition to use this method is that input array should in sorted array. Otherwise it wont work.

How Binary Search works: It will search for the element key in a sorted array of elements in such away that, it finds the middle element of the array by getting average of  starting and ending postions of the array, if the middle element is key , search stops and returns the position of the element other wise key will be compared with mid element, and if the mid element is greater than the key value, starting index of the array changes to mid+1, and the mid value is less than the key value, ending index of the array changes to mid-1. This process continues until key value finds or starting index greater than equal to the ending index.

Algorithm for Binary Search:

1. Get the key element which needs to be searched
2. Get the sorted array in which key needs to be searched
3. Find the mid value of the array by findings (startIndex+ endIndex)/2
4. If key value is equals the array[mid] value , returns mid value and stop the search
5. If the key value greater than array[mid] value, change the startIndex to mid+1 and goto step 3.
6. If the key value less than array[mid] value, change the endIndexto mid-1 and goto step 3.
7. Repeat the steps 3 to 6 until startIndex greater than equal to the endIndex.

Function Prototype for Binary Search: This function will takes the input values like array of elements,key which needs to be searched in the array, starting posting of the array and ending position of the array. It will return the position of the finding element or -1 if not found in the array.

/****************************************************************
Name:       binary_search
Input: array , key , max_pos, min_pos
Return type: int

****************************************************************/
int binary_search(int arr[],int key,int min_pos, int max_pos)
{
    while(max_pos >= min_pos)
    {
        //finding the middle element
        int mid = (min_pos + max_pos)/2;
        // if mid element is less than key, need to change min_pos value
        if(arr[mid]<key)
            min_pos = mid+1;
        // if mid element is greate than key, need to change max_pos value
        else if(arr[mid]>key)
            max_pos = mid-1;
        // else got the position
        else
            return mid;
    }
    //other wise not in the array
    return -1;
}


Time Complexity: The time complexity of the Binary search is O(log(n)). This is because, each time it will eliminate half of the array. So at max we will get log(n) iteration to search. Assume that if the array has 8 elements, for first iteration, we will get 8/2 which is 4 and for second iteration we will get 4/2 which is 2 and in third itetation we will get 2/2 which is 1. Like this if the elements are 128, we will get in log(128) iteration which is 7 iterations.


Program of Binary search in  C: Below is the binary search C code.
#include

/****************************************************************
Name:       binary_search
Input: array , key , max_pos, min_pos
Return type: int

****************************************************************/
int binary_search(int arr[],int key,int min_pos, int max_pos)
{
    while(max_pos >= min_pos)
    {
        //finding the middle element
        int mid = (min_pos + max_pos)/2;
        // if mid element is less than key, need to change min_pos value
        if(arr[mid]<key)
            min_pos = mid+1;
        // if mid element is greate than key, need to change max_pos value
        else if(arr[mid]>key)
            max_pos = mid-1;
        // else got the position
        else
            return mid;
    }
    //other wise not in the array
    return -1;
}

 
main()
{
    int arr[10],i,pos,key;
    int startIndex=0;
    int endIndex=9;
    printf("enter the elements in array in sorted orderd only\n");
    for(i=0;i<10;i++)
    {
        scanf("%d",&arr[i]);
    }
    printf("enter the element to be searched\n");
    scanf("%d",&key);
    pos = binary_search(arr,key,startIndex,endIndex);
    if(pos!=-1)
        printf("element %d find at position %d",key,pos);
    else
        printf("element not in the array\n");
}

Results:
enter the elements in array in sorted orderd only
10
20
30
40
50
60
70
80
90
100
enter the element to be searched
20
element 20 find at position 1



enter the elements in array in sorted orderd only
10
20
30
40
50
60
70
80
90
100
enter the element to be searched
199
element not in the array

Thursday, May 3, 2012

Sorting and Searching Techniques!!!

In Computer Science, Sorting and Searching are the two basic operations which we will come across frequently. There are many algorithms are available to do Sorting and Searching depending on time complexity and space complexity.

Sorting: Sorting is a technique to arrange the elements in  a proper order like ascending or descending order.
There are many sorting techniques available which are used depending on the no. of elements to sort. Generally time complexity of the sorting technique is Big O of n^2 or O(n^2) where n is the no. elements in the array.

  • Bubble Sort
  • Insertion Sort
  • Selection Sort
  • Quick Sort
  • Merge Sort
  • Heap Sort


Searching: Searching is a technique to find the element from a group of elements. There are many techniques to Search the element in a group of element depending on the efficiency. generally time complexity of the searching technique is Big O of n or O(n) where n is the no.of elements in an array.


Time Complexity: Time complexity for the Sorting and searching is measured in Big O notation. This will represents efficiency of the techniue. It will be measures in three ways namely Best, average and worst cases.
Generally Best , average and worst cases for Sorting are same and it is O(n^2). But They may vary depending on the sorting technique we used. For example for Quick Sort worst case is O(n^2) where as best and average time complexit is O(n*log n).

Comparison of Sorting techniques:

Comparison of sorting techniques

For Searching Best case will be O(1) and worst case and average case will be O(n). similar to Sorting, searching time complexity also varies depending on the technique. For example for Binary search best case will be O(1) where as average and worst case will be O(log n).

Comparison of Searching techniques:
Comparison of searching techniques

Popular Posts