Binary search is a fundamental algorithm in computer science. It is used to find the position of a given integer in a sorted list of integers. We don't have to iterate through the whole list, if we use this algorithm. Therefore it is an efficient algorithm for searching. The complexity of binary search algorithm is O(logN).
http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBinarySearch.html
If N elements are there in the list,
you will have to halve the list x times to find an element. (Halve the list until 1 element is left)
1 = N / 2x
2x = N
x = log2 N
Therefore time complexity - O(logN)
[code]
#include <stdio.h>
int main()
{
int arr[100];
int n, i, el;
printf("Enter the number of elements: ");
scanf("%d",&n);
printf("Enter the elements\n");
for(i = 0; i<n; i++)
{
scanf("%d",&arr[i]);
if(i != 0 && arr[i-1]>arr[i])
{
printf("Please enter a sorted list!\n");
return 0;
}
}
printf("Enter the element to search\n");
scanf("%d",&el);
int position = binarySearch(arr,n,el);
if(position != -1)
printf("The element is at %d.\n",position);
else
printf("Element not found!\n");
return 0;
}
/*Binary search function
Arguments - integer array
size of the array
element to search for
Return the position if successful
*/
int binarySearch(int arr[], int size, int el)
{
int low = 0, high = size-1;
int mid = (high + low)/2;
while(arr[mid] != el)
{
if(arr[mid] > el)
high = mid;
else
low = mid;
if(high == low+1)
{
if(arr[high] == el)
return high;
else if(arr[low] == el)
return low;
else
return -1;
}
mid = (low + high)/2;
}
return mid+1;
}[/code]
Subscribe to:
Post Comments (Atom)
Optimized quick sort
In the previous article we discussed about quick sort algorithm. In this article we are going to discuss about further optimizing quick sor...

-
Garlic Garlic is a very widely used herb in lowering both cholesterol and triglycerides. It also has anti-clotting and anti-bacterial proper...
-
We are all fully aware of the anti-biotic resistant bacteria, which exists in our hospitals. There are all sorts of fungus, viruses, disease...
-
Vert.x is a toolkit for building reactive applications on the JVM. For more information about vert.x please read the previous article from...
No comments:
Post a Comment