Sunday, 17 September 2017

Implementation of Binary Search algorithm in C language with its Pros and Cons

In Binary search algorithm, we tried to find out the search element in an already sorted linear array by repeatedly dividing it into equal half. After dividing into equal half compare the search_element with the array element which is at the middle position. If the search_element is equal the array element then search is successful other check whether search element is greater then of less then the middle position element.
If the search_element is less then the middle position element then it means your search_element is present in the left side sub array.
If the search_element is greater then the middle position element then it means your search_element is present in the right side sub array.

In best case the time complexity of the linear search algorithm is O(1) and average and worst case time complexity is O(log2(n)), where n is the size of the linear array.

Pros and Cons of Binary Search algorithm:

Pros:
1. This search algorithm is suitable for the sorted data.
2. It is suitable for the large list of data elements.
3. This search is suitable for storage structure that support direct access.
4. Time complexity of this search algorithm is O(log2(n)).

Cons:
1. This algorithm is not suitable for unsorted data/elements.
2. This search is suitable for storage structure that do not support direct access.
3. This is inefficient for small data/elements.

 
Below is the step which we follow to implement Binary Search algorithm are:

1. First declare all the header fill you want in your program ( according to language in which you want to implement the algorithm).
2. Declare an array of any size ( i.e arr[15]) with different variable you need (like search_element, i and j for loop variable) and index variable low =0 and high = n.
3. Enter element into the array arr[15].
4. Enter the search element search_element
5. find the middle element until high is greater then low
6. If search_element is equal to the middle element, then we say the search is successful.
7. If search_element is greater then middle element, then it means the search_element is in the right sub array. In this case change low to middle+1.
8. If search_element is less then middle element, then it means the search_element is in the left sub array. In this case change high to middle-1.
9. Repeat step 5 to 8 until condition is true.
10. End of the program.
 
Implementation of Binary Search Algorithm in C:
#include<stdio.h>
int main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements\n");
scanf("%d",&n);
for (c = 0; c < n; c++)
scanf("%d",&array[c]);
printf("Enter value to find\n");
scanf("%d", &search);
first = 0;
last = n - 1;
while (first <= last)
{
middle = (first+last)/2;
if (array[middle] < search)
{
first = middle + 1; 

else if (array[middle] == search)
{
printf("%d found at location %d.\n", search, middle+1);
break;
}
else
{
last = middle - 1;
}
}
if (first > last)
printf("Not found! %d is not present in the list.\n", search);
return 0;  
}

Online Compiler Link for the above code: Run the above program online

Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput