Adobe Interview Question MTSs
Country: India
Interview Type: In-Person
private static int circularBinSearch ( int key, int low, int high )
{
if (low > high)
{
return -1; // not found
}
int mid = (low + high) / 2;
steps++;
if (A[mid] == key)
{
return mid;
}
else if (key < A[mid])
{
return ((A[low] <= A[mid]) && (A[low] > key)) ?
circularBinSearch(key, mid + 1, high) :
circularBinSearch(key, low, mid - 1);
}
else // key > A[mid]
{
return ((A[mid] <= A[high]) && (key > A[high])) ?
circularBinSearch(key, low, mid - 1) :
circularBinSearch(key, mid + 1, high);
}
}
This one works in log n
private static int _findInRotatedArray(int[] arr, int n, int leftIndex, int rightIndex){
int len = rightIndex - leftIndex + 1;
if(len == 1) return arr[leftIndex] == n ? leftIndex : -1;
boolean isRotated = arr[leftIndex] > arr[rightIndex];
if(!isRotated && !(arr[leftIndex] <= n && arr[rightIndex] >= n)) return -1;
int left = _findInRotatedArray(arr, n, leftIndex, (int) (rightIndex - Math.ceil(len/2)));
return left > -1 ? left :_findInRotatedArray(arr, n, (int) (leftIndex + Math.floor(len/2)), rightIndex);
}
bool search(int a[],int begin,int end,int x)
{
if(begin > end)
{
return false;
}
else
{
int middle = (begin+end)/2;
if(a[middle] == x)
{
cout<<middle;
return true;
}
else
{
if(a[begin] > a[middle])
{
if(x < a[middle])
{
return search(a,begin,middle-1,x);
}
else
{
if(x < a[begin])
{
return search(a,middle + 1,end,x);
}
else
{
return search(a,begin,middle-1,x);
}
}
}
else
{
if(x > a[middle])
{
return search(a,middle + 1,end,x);
}
else
{
if(x < a[begin])
{
return search(a,middle+1,end,x);
}
else
{
return search(a,begin,middle-1,x);
}
}
}
}
}
}
int findElement(int a[],int n, int val)
{
int start = 0;
int end = n-1;
int mid = (start+end)/2;
while(start <= end)
{
if(a[mid] == val)
return mid;
// if mid value is less than search value.
if(a[mid] < val)
{
// check if end value is smaller than search value.
// if it is we need to search in start to mid-1
// else search in mid+1 to end
if(a[end] < val)
end = mid-1;
else
start = mid+1;
}
// mid value is greater than search value.
else
{
// if mid is greater than end i.e. sub-array after this is not in increasing order (contais pivot element)
// search in mid+1 to end.
// Else search in start to mid-1.
if(a[mid] > a[end])
start = mid+1;
else
end = mid -1;
}
mid = (start+end)/2;
}
}
int main()
{
int a[] = {90,100,110,10,20,30,40,50,60,70,80};
int size = sizeof(a)/sizeof(a[0]);
int n;
while(true)
{
cout<<"\nENTER NUMBER : ";
cin>>n;
cout<<"\nFOUND AT : "<<findElement(a,size,n)<<"\n\n";
}
}
compare mid element with the first and last to decide where is the incorrect order present in the array(1st half r 2nd half) and do it until you will reach a stage where the mid element is known to be in incorrect order(rotated part)
2) After that,do binary search selecting any of the 2halves(in the upper stack like division we did) until you find the element.
Example:
Suppose, in 7 8 9 0 1 2 3 4 5 6
->mid element is 2
2<7 => first half is incorrect
So, the mid element is in the rotated part of array
->Now,compare x with last element in the rotated part. Supposing 9 here,
9>6 => 9 is in the 1st half of the array
and then by using binary search in the 1st part of array,we can search for a given element in O(log n) time complexity
Correct me if i an wrong.. :)
int[] array = { 5, 6, 10, 11, 12, 1, 2, 3 };
int lengthOfArray = array.length;
int begIndex = 0;
int endIndex = 0;
int searchElement = 10;//element need to be search
if (array[0] < array[lengthOfArray / 2]) {
if (searchElement <= array[lengthOfArray / 2]
&& searchElement >= array[0]) {
begIndex = 0;
endIndex = (lengthOfArray / 2) - 1;
} else if (searchElement <= array[0]) {
begIndex = lengthOfArray / 2;
endIndex = lengthOfArray - 1;
}
}
else {
if (searchElement >= array[lengthOfArray / 2]
&& searchElement <= array[0]) {
begIndex = (lengthOfArray / 2);
endIndex = lengthOfArray - 1;
} else if (searchElement >= array[lengthOfArray / 2]
&& searchElement >= array[0]) {
begIndex = 0;
endIndex = (lengthOfArray / 2);
}
}
for (int i = begIndex; i <= endIndex; i++) {
if (array[i] == searchElement) {
System.out.println(searchElement + " is at location :"
+ (i + 1));
break;
}
}
#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;
boolean search(int a[],int left,int right,int value)
{ int mid=(left+right)/2;
boolean t,m,p,q;
if(a[mid]==value)
{
return true;
}
else if(left<=right)
{ if(a[mid]>a[0])
{ if(value>a[0])
t=search(a,left,mid,value);
else
m= search(a,mid+1,right,value);
}
else if(a[mid]<a[0])
{ if(value<a[0])
p= search(a,mid+1,right,value);
else
q=search(a,left,mid,value);
}
}
else
return false;
return p||q||t||m?true:false
}
int main()
{ int a[]={ 10,12,15,17,2,4,5,6,8,9};
boolean x= search(a,0,9,3);
if(x)
cout<<"present\n";
else
cout<<"not present \n";
system("pause");
return 0;
}
Logic:
1. Array is given with n elements. and we have to search an element say x.
2. take the mid element.
Its for sure, one half of array will be in correct order.
find half array with correct order. You can find it by comparing mid element with either
first element or last element.
3. If x lies in half array with correct order, do the binary search on this half.
Otherwise, repeat step 2 and 3.
for ex: 7 8 9 0 1 2 3 4 5 6 and suppose we have to search element say 9.
here the correct half order is 2 3 4 5 6 and 9 is not part of it.
so again we will process first half array 7 8 9 0 1
here correct half order is 7 8 9 and element 9 lies in this.
so we will perform binary search on this.
This complete process will take log(n) time.
I cannot figure out how can we determine the correct half order by just comparing it with first and last element of that half.
@nitin: (We will say elements are in correct order if they are in increasing order from left to right )
Now
->Take the middlemost element
->compare it with first element
if first element is less that the middle element ,first half is in
correct order
So sry
Continue:
if middle element is less than last element,then this part is in correct order.
Let's take an example:
5 6 7 8 9 1 2
Here middle element is 8.As 5<8,clearly first half is in correct order.
Please let me know in case of you have any counter example for this explaination
- CodeSpace October 07, 2012int findElement(int value, int array[]){ return(modifiedBinarySearch(value, array, 0, array.length); } // Modified binary search function that detects rotation in array // and compensates accordingly. int modifiedBinarySearch(int value, int array[], int start, int end){ // Base case for recursive method if(end - start <= 1){ if(array[start] == value) return(start); else if(array[end] == value) return(end); else return(-1); } int mid = (start + end) / 2; // Another exit base case if(array[mid] == value) return(mid); if (array[start] < array[mid]) && array[start] < value && array[mid] > value) // First half of array is not rotated and value is within its range return(value, array, start, mid); if (array[start] > array[mid]) && (array[start] < value || array[mid] > value)) // First half of array is rotated and value is within its range return(value, array, start, mid); if (array[mid] < array[end]) && array[mid] < value && array[end] > value) // Second half of array is not rotated and value is within its range return(value, array, mid, end); if (array[mid] > array[end]) && (array[mid] < value || array[end] > value)) // Second half of array is rotated and value is within its range return(value, array, mid, end); // Value is not is array return(-1); }