Algorithms/BitonicArray.java at master · ranavivek04/Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class BitonicArray{


private static int findBitonicPoint(int a[]){
           int n = a.length;
           int lo = 0;
           int hi = n-1;
           while (lo <= hi){
                 int mid = lo + ( hi - lo ) / 2;
                 if ( a[mid] > a[mid-1] && a[mid]<a[mid+1])
                      lo=mid+1;
                 if( a[mid]<a[mid-1] && a[mid]>a[mid+1] )
                      hi=mid-1;
                 if( a[mid]> a[mid-1] && a[mid]>a[mid+1])
                      return mid;
                  }
            return -1;
         }

private static int findLeft(int a[],int n){
        int lo = 0;
        int hi = findBitonicPoint(a);
        while ( lo <= hi ) {
             int mid = lo + (hi - lo)/2;
             if (n < a[mid])
               hi = mid - 1;
             else if ( n > a[mid] )
                  lo = mid + 1;
             else return mid;
               }
          return -1;
}

private static int findRight(int a[],int n){
        int l = a.length;
        int lo = findBitonicPoint(a)+1;
        int hi = l-1;
        while ( lo <= hi ) {
             int mid = lo + (hi - lo)/2;
             if (n < a[mid])
              lo = mid + 1;
             else if ( n > a[mid] )
                   hi = mid - 1;
             else return mid;
               }
          return -1;
}

public static int find(int[] a,int n){
      return BitonicArray.findLeft(a,n)==-1 ? BitonicArray.findRight(a,n) :BitonicArray.findLeft(a,n);


}
public static void main(String[] args){
int arr[]={2,3,5,7,9,11,13,4,1,0};
System.out.println(BitonicArray.findBitonicPoint(arr));
System.out.println(BitonicArray.findLeft(arr,3));
System.out.println(BitonicArray.findRight(arr,0));
System.out.println(BitonicArray.find(arr,3));
System.out.println(BitonicArray.find(arr,0));

   }
}