Given an array of N distinct integers with the property that there exists an index K (0 <= K <= N-1) such that input[0], ..., input[K] is and increasing sequence and input[K], ..., input[N-1] is a decreasing sequence. Devise and algorithm to find K. Ex [1 2 4 7 10 15 13 11 5 0 -5] Answer: K=5 (input[K]=15)
courtesy: Vibhaj
Click here to see the solution.
p.s. - For Remarks please hit the given link once. For Hint, hit it twice and for the solution, hit it thrice.
Hints: Value stored in any element of the Array reaches a maxima at certain index. |
|
Solution:
Use binary search with the following conditions :
input[mid-1] < input[mid] > input[mid+1] for mid != 0 and mid != N-1
input[mid] > input[mid+1] for mid == 0
input[mid-1] < input[mid] for mid == N-1 with initial low = 0, high = N-1, mid = (high + low)/2
int bitonic_pivot(int input[], int N)
{
int low=0, high=N-1, mid;
while(low < high)
{
mid=(low+high)/2;
if((!mid || (input[mid-1] < input[mid])) && (mid != N-1 || (input[mid] > input[mid+1])))
return mid;
else if((!mid || (input[mid-1] < input[mid])) && (mid != N-1 || (input[mid] < input[mid+1])))
low=mid+1;
else if((!mid || (input[mid-1] > input[mid])) && (mid != N-1 || (input[mid] > input[mid+1])))
high=mid;
}
return -1;
}
|
|
|
Posts
