An array is said to be biotonic if it contains distinct integers such that, the array is monotonically increasing upto index k and then monotonically decreasing.

If the array is plotted on a graph, it forms a mountain-like structure.

The naive approach is to use Linear Search, which runs in O(N) time. The time complexity can be reduced to O(log(N)) using Binary Search.

Incorrect Algorithm

Edit (5th Feb) : The following algorithm and code is incorrect for the given problem.

This algorithm is incorrect, because I assumed that, target will surely lie in sorted half, but since in the other half, the element can be present, the following algorithm fails.

I found this mistake by dry-running the code for target==4 on the given array.

In every iteration, check which half is sorted, then if target lies in the sorted half move in its direction else move in opposite direction.

int biotonic_search(int arr[], int n, int target){
  int ans = -1, start =0, end = n-1;
  int mid;
  while(start <= end){
    mid = start + end - 1;
    if(arr[mid] == target){
      ans = mid;
      break;
    }
 
    if(arr[start] < arr[mid]){
      if(target>= arr[start] && target < arr[mid]){
        end = mid - 1;
      }else{
        start = mid + 1;
      }
    }else{
      if(target>arr[mid] && target<= arr[end]){
        start = mid + 1;
      }else{
        end = mid - 1;
      }
    }
  }
}

Correct Algorithm

The correct algorithm for this problem is:

1. Find the index k, of the maximum element in biotonic array.
2. ans1 <- binary_search(arr,0,k,target) 
3. ans2 <- binary_search(arr,k+1,n,target)
4. If ans1!=-1, return ans1
5. If ans2!=-1, return ans2 

The following problems can also be solved by using same approach:

1. Find maximum element in a biotonic array.
2. Find minimum element in a rotated sorted array.
3. Search an element in a rotated sorted array.

Refer to the code for the above problems here