Search An Element in Bitonic Array

Problem statement:

Given an bitonic array, find the max element in that.

Example:

Array {1, 2, 3, 4, 5, 4, 3, 2, 1};

key = 1

Output = 0 or 9

A bitonic array is an ascending sorted array where, after a particular element, the array starts descending.

In our example above, the array is ascending till element 5 and starts descending after that.

Solution:

We can solve this with help of binary search and peak element.

First we need to find the peak element and dvide the array into 2 halves.

Then apply binary search in both of the halves.

Solution:

#include <iostream>
using namespace std;

int find_peak_element_index(int arr[], int len) 
{ 
    int start = 0;
    int end = len - 1;
  
          while (start <= end) 
          {
              int mid = (start + end) / 2;
  
              if ((mid == 0 || arr[mid - 1] <= arr[mid]) && (mid == len - 1 || arr[mid] >= arr[mid + 1])) 
              {
                  return mid;  
              } else if (mid > 0 && arr[mid - 1] > arr[mid]) 
              {
                  end = mid - 1;
              } else {
                  start = mid + 1;
              }
        } 
    return -1;
}


int ascending_binary_search(int arr[], int start, int end, int key)
{
   while (start <= end) 
   { 
       int mid = start + (end - start) / 2; 
       if (arr[mid] == key) 
           return mid; 
       if (arr[mid] > key) 
           end = mid - 1; 
       else
           start = mid + 1; 
   } 
    return -1;

}

int descending_binary_search(int arr[], int start, int end, int key)
{
   while (start <= end) 
   { 
       int mid = start + (end - start) / 2; 
       if (arr[mid] == key) 
           return mid; 
       if (arr[mid] < key) 
           end = mid - 1; 
       else
           start = mid + 1; 
   } 
    return -1;
}


int binary_search( int arr[], int len, int peak_index, int key)
{
    if (key > arr[peak_index])
        return -1;

    else if(key == arr[peak_index]) 
        return peak_index;
    else
    {   
        int temp = ascending_binary_search(arr, 0, peak_index - 1, key); 
        if (temp != -1) 
        { 
             return temp; 
        }    
        return descending_binary_search(arr, peak_index + 1, len - 1, key); 
    }  
}

int main(void) 
{ 
    int arr[] = {1, 2, 3, 4, 5, 4, 3, 2, 1}; 
    int len = sizeof(arr) / sizeof(arr[0]); 
    int key = 1;
    int peak_index = find_peak_element_index(arr, len);
    int result = binary_search(arr, len, peak_index, key);

    cout<<"The key element "<<key<<" is found at the index " <<result<<endl;

    return 0; 
} 

Output:

The key element 1 is found at the index 0