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

No comments:

Popular Posts