dnair89
BAN USER
Comments (3)
Reputation 10
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 1 vote
- Pretty straight forward, given a sorted array find if an element exists using binary search. Complexity: O(logn)
- Find pivot = (left+right)/2, check if data == Arr[pivot], if yes return 1
- else if data<Arr[pivot], search in left half recursively
- if bigger search in right half recursively
- do till left>right
int binarySearch(int arr[],int x,int l,int r)
{
int pivot = (l+r)/2;
if(l>r)return 0;
if(x == arr[pivot])return 1;
else
{
if(x<arr[pivot]) return binarySearch(arr,x,l,pivot-1);
else return binarySearch(arr,x,pivot+1,r);
}
}
void main()
{
int arr[5] = {12,18,22,54,63};
int x = 22;
if(binarySearch(arr,x,0,4))printf("Found %d",x);
else printf("Did not Find %d",x);
}
Output: Found 22
- dnair89 March 12, 2012Comment hidden because of low score. Click to expand.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
Output: 3
- dnair89 March 12, 2012Works even for negative numbers, tried it!