DEV Community

Prashant Mishra
Prashant Mishra

Posted on

Find target in bitonic array with unique elements

TC : O(logn)


class Main {
    public static void main(String[] args) {
        int arr[] = {1,3,6,8,5,4,2};
        int target = 2;
        //find index of 5 in the array
        int peakIndex = findPeak(arr,0,arr.length-1);
        int index = findIndex(arr, target, 0,peakIndex, true);
        if(index!=-1) System.out.println(index);
        System.out.println(findIndex(arr,target, peakIndex+1, arr.length-1, false));

    }
    public static int findIndex(int arr[], int target,int l, int h, boolean increasing){

        while(l<=h){
            int mid = (l+ h) /2;

            if(arr[mid] == target )return mid;

            if(increasing){
                if(arr[mid]<target) l=  mid+1;
                else h = mid-1;
            }
            else{
                if(arr[mid] > target) l = mid+1;
                else h = mid-1;
            }
        }
        return -1;
    }
    public static int findPeak(int arr[], int l, int h){
        while(l<h){
            int mid = (l + h) /2;
            if(arr[mid] < arr[mid+1]) l = mid + 1;
            else h = mid;
        }
        return l;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)