|
search a number in a sorted array of the form....
Microsoft Interview Questions and Answers
(Continued from previous question...)
64. search a number in a sorted array of the form....
Question:
search a number in a sorted array of the form
eg: 4 5 6 1 2 3
in O(logn).
maybe an answer:
int binarySearch(int a[], int key, int low, int high)
{
if(low > high)
return -1;
int mid = (low + high) / 2;
if( key == a[mid] )
return mid;
int result(-1);
if( key < a[mid] )
{
if( key >= a[low] && key <= a[mid-1] )
result = binarySearch(a, key, low, mid-1);
else
result = binarySearch(a, key, mid+1, high);
} else {
if( key >= a[mid+1] && key <= a[high] )
result = binarySearch(a, key, mid+1, high);
else
result = binarySearch(a, key, low, mid-1);
}
return result;
}
maybe an answer2:
int search(int a[],int l,intr,int x)
{
while(l<=r)
{
mid=l+(r-l)/2;
if(a[mid]==x)
retun mid;
else if(a[l]<=a[mid])
{
if(x>a[mid])
l=mid+1;
else if(x>=a[l])
r=mid-1;
else
l=mid+1;
}
else if(x<a[mid])
u=mid-1;
else if(x<=a[r])
l=mid+1;
else
u=mid-1;
}
}
maybe an answer3:
int search (char * a , char x) {
int low=0;
int up =sizeof(a)-1;
int mid= low+up-low/2;
while(low<=up) {
if (x==a[mid]) {
return x;
}
if(a[low] < a[mid]){
if (x<a[mid])
up=mid-1;
else
low=mid+1;
}
else if(x > a[mid])
r=mid-1;
else
l=mid+1;
}
}
(Continued on next question...)
Other Interview Questions
| 