Algorithms Forever ...: Bitonic array
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)
Ex [1 2 4 7 10 15 13 11 5 0 -5]
Answer: K=5 (input[K]=15)
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
Code :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;
}
Read full article from Algorithms Forever ...: Bitonic array
