Interview Question
Country: United States
It would be fun, if the problem would have been like this
A[1] <= A[2] <= ..... <= A[n]
Then it would have become more complex because of duplicates.
binary search will do.
pseudocode:
{
binarysearch(i, begin, end){
middle = (begin+end)/2
if(A[middle]==i) return middle
else if (A[middle]< i) call binarysearch(i,middle+1,end)
else call binarysearch(i, begin,middle-1)
}
1) If A[n]<n then there is no such element exists as A[1] < A[2] <...< A[n]..
2)if A[1]>1 then there is no such element exists as A[1] < A[2] <...< A[n]..
Above two conditions are also important..
yes, that part is missing
pseudocode is modified adding those conditions:
binarysearch(i, begin, end){
middle = (begin+end)/2
if(A[middle]==i) return middle
else if (A[middle]< i) call binarysearch(i,middle+1,end)
else if (A[middle]> i) call binarysearch(i, begin,middle-1)
else "no such element exists"
}
/* Locates an index i such that A[i] = i
array - input sorted list
from - from index
to - to index
returns an i such that A[i] = i; otherwise -1.
*/
int bin_search_index_match(int* array, int from, int to)
{
/* if the first elt is bigger than its index then we stop searching
because our input list is sorted and increasing. No index can catch the content */
if(array[from] > from)
return -1;
int mid = from + (to - from)/2;
if(array[mid] == mid)
return mid;
if(array[mid] > mid)
return bin_search_index_match(array, from, mid-1);
else
return bin_search_index_match(array, mid+1, to);
}
check middle element if i<a[i] go for first half middle, else right half middle. continue process till we find the answer.
- master May 03, 2013