### Search in a bitonic array sortedarray array searching bitonicarray    Posted: 6 years ago Updated: 5 years ago Edit answers (1) views (10361) 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 2 years ago @li4dro

 Posted: 6 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);}