Binary Search:
Binary search is a fast searching algorithm that searches an element in a sorted array. This search works on the principle of the divide and conquer paradigm.
§ Working Process:
To perform binary search on an array sorted in ascending order first we have to calculate the middle index of the array, then the search element is searched in the middle of the array. If the element is smaller than the middle element, then binary search is performed on the left sub-array otherwise the binary search is performed on the right sub-array.
§ Algorithm:
Algorithm BinarySearch(a,i,l,x)
{
// a = array
// i = starting index
// l = end index
// x = element to be searched
if(l=i)
{
if(x=a[i])
{
return i;
}
else
{
return 0;
}
}
else
{
if(x=a[mid])
{
return mid;
}
else if(x<a[mid])
return BinarySearch(a,i,mid-1,x)
else
return BinarySearch(a,mid+1,l,x)
}
}
§ Analysis:
If T(n) represents the total computing time required to find the element x using binary search on an array of n elements, then the recurrence relation can be represented as:
§ Solution:
No comments:
Post a Comment