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)

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 :

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;

}

Complexity :

• Time : O(log N)
• Space : O(1)