• 1

Search in a bitonic array
  • sortedarray
  • array
  • searching
  • bitonicarray
  •   
    subscribe
  • Posted: 7 years ago
  • Updated: 6 years ago
  • Edit
  • answers (1)
  • views (13222)
  • Comments (1)

Suppose you are given a bitonic array. How will you determines whether a given integer is in the array or not?


not work for this case {1,3,2,1} - posted 4 years ago @li4dro

Posted Answers

  • Posted: 7 years ago
  • 0 0
  • Edit

A bitonic array is comprised of an increasing sequence of integers followed immediately by a decreasing sequence of integers. To perform a search operation in a bitonic array :


  • Find the maximum element of the array by finding the end of the increasing part of the array using modified binary search.
  • Search the increasing part of the array using binary search.
  • If the element we are looking for is found in the last step, result found. If not, search the decreasing part of the array using binary search.


For simplicity, let us assume that the array has distinct integers. So the element we are looking for will be either at the increasing or decreasing part of the array.

Number of comparisons to find the largest element, in the worst case = logn
Number of comparisons to find the element in the increasing part of the array = \( logn_1 \)
Number of comparisons to find the element in the decreasing part of the array = \( logn_2 \)
where \( n_1+n_2 = n \) = number of elements in the array
Therefore, total number of comparisons = 3logn 


public static int findMax (int[] array, int low, int high){

      if(array.length  < = 2)
            return -1;

      int middle = (low+high)/2;
      if(low == middle || middle+1 == high)
            return -1;

      /* If middle element is the largest element in the array */
      if(array[middle] > array[middle-1]  & &  array[middle] > array[middle+1])
           return middle;

      int n1 = findMax (array, low, middle);
      int n2 = findMax (array, middle, high);
      /* If element is found in the increasing part of the array */
      if (n1! = -1)
          return n1;
      /* If element is found in the decreasing part of the array */
      if (n2! = -1)
          return n2;

      return -1;
 }

public int searchInBitonicArray (int[] array, int key){

      int  max = findMax (array, 0, array.length);
      /* Search increasing part of the array using binary search */
      int k = binarySearch (array, 0, max, key, true);
      if (k! = -1)
          return k;
      else
          return binarySearch (array, max+1, array.length, key, false);
}
You need to Sign In to post your solution.