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...
-
Graph A graph ‘G’ is defined as G = (V, E) Where V is a set of all vertices and E is a set of all edges in the graph. Example In the...
-
What is Vert.x ? Vert.x is a toolkit for writing scalable, polyglot, reactive applications which run on the JVM. Vert.x is similar to...
-
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